13161번: 분단의 슬픔

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

임의의 i, j에 대해 용량이 w[i, j]인 i->j 간선을 생성한다.
A 진영에 속한 i번 사람에 대해 용량이 inf인 source -> i 간선을 생성한다.
B 진영에 속한 i번 사람에 대해 용량이 inf인 i -> sink 간선을 생성한다.
이 그래프에서 최대 유량이 답이 된다.
그 이유는 최대 유량 = 최소 컷이고, 컷은 곧 두 진영으로 나누었을 때 슬픔 정도이기 때문이다.

Dinic's algorithm을 사용해야 한다.

시간복잡도는 $O(n^4)$

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int fl[502][502], n, res, lv[502], c[502];
bool bfs() {
    fill(lv + 1, lv + n + 2, -1);
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (int i = 0; i <= n + 1; i++) if (!~lv[i] && fl[h][i]) lv[i] = lv[h] + 1, q.push(i);
    }
    return ~lv[n + 1];
}
int dfs(int h, int x) {
    if (h == n + 1) return x;
    for (int &i = c[h]; i <= n + 1; i++) if (lv[h] < lv[i] && fl[h][i]) {
        int ret = dfs(i, min(x, fl[h][i]));
        if (ret) {
            fl[h][i] -= ret;
            fl[i][h] += ret;
            return ret;
        }
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x == 1) fl[0][i] = 1e9;
        if (x == 2) fl[i][n + 1] = 1e9;
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", fl[i] + j);
    while (bfs()) {
        fill(c, c + n + 2, 0);
        for (int ret; ret = dfs(0, 1e9);) res += ret;
    }
    printf("%d\n", res);
    for (int i = 1; i <= n; i++) if (~lv[i]) printf("%d ", i);
    puts("");
    for (int i = 1; i <= n; i++) if (!~lv[i]) printf("%d ", i);
    puts("");
    return 0;
}