딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/2316

이 문제에서는 도시를 한번만 방문하면서

최대 유량을 구해야한다.

도시를 한번만 방문해야하는 조건을 구현하기 위해

정점을 분할해주어야한다.

정점을 분할해주고 정점과 정점' 를 연결해주는 간선의 Capacity를 1로 두면

해당 정점을 최대 한 번만 방문하도록 할 수 있다.

#include <bits/stdc++.h>
using namespace std;

const int MAX = 810;
int n, p, res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(d, d + MAX, -1);

        queue<int> Q;
        Q.push(start);
        d[start] = 0;

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();

            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;

                    if (nx == end) break;
                }

            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }
        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }
}



int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> p;

    for (int i = 1; i <= n; i++) {
		int x = 2 * i;
        int x_ = 2 * i - 1;

        c[x][x_] = 1;
        adj[x_].push_back(x);
        adj[x].push_back(x_);
    }

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        int u = a * 2;
		int u_ = a * 2 - 1;

		int v = b * 2;
        int v_ = b * 2 - 1;

        c[u_][v] = 1;
        c[v_][u] = 1;
        adj[u_].push_back(v);
        adj[v].push_back(u_);

        adj[v_].push_back(u);
        adj[u].push_back(v_);
    }

    maxFlow(1, 4);

    cout << res << '\n';
    return 0;
}