(라이님 블로그 대회 알고리즘 따라잡기 28) 디닉 알고리즘(Dinic's Algorithm)

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220812858041&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList\

디닉 알고리즘(Dinic's Algorithm) (수정: 2016-09-19)

 

시간복잡도 O(V^2E) 알고리즘인 이 알고리즘은 에드몬드 카프 알고리즘이 O(VE^2)이였던 알고리즘에 비해 빠른 알고리즘이다!

 

설명은 라이님 블로그를 참고할 것!

 

코드는 크게 

BFS를 이용해 레벨 그래프를 구축하는 과정과 DFS를 이용해 차단 유량을 계산하는 두 부분으로 나뉜다.

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1000000000;

int N, S, E;
vector<vector<int>> c, f, adj;
vector<int> level, work;

// 디닉 전용 bfs 함수: 레벨 그래프 구축
bool bfs() {
    fill(level.begin(), level.end(), -1);
    level[S] = 0;

    queue<int> Q;
    Q.push(S);
    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();
        for (int next : adj[curr]) {
            if (level[next] == -1 && c[curr][next] - f[curr][next] > 0) {
                level[next] = level[curr] + 1;
                Q.push(next);
            }
        }
    }
    return level[E] != -1;
}

// 디닉 전용 dfs 함수: 차단 유량 계산
int dfs(int curr, int dest, int flow) {
    if (curr == dest) return flow;

    for (int &i = work[curr]; i < adj[curr].size(); i++) {
        int next = adj[curr][i];
        if (level[next] == level[curr] + 1 && c[curr][next] - f[curr][next] > 0) {
            int df = dfs(next, dest, min(c[curr][next] - f[curr][next], flow));
            if (df > 0) {
                f[curr][next] += df;
                f[next][curr] -= df;
                return df;
            }
        }
    }
    return 0;
}

int main() {
    // 그래프 정보 입력받기 및 초기화
    scanf("%d", &N);
    S = N;
    E = N + 1;
    c.assign(N + 2, vector<int>(N + 2, 0));
    f.assign(N + 2, vector<int>(N + 2, 0));
    adj.assign(N + 2, vector<int>());

    for (int i = 0; i < N; i++) {
        int team;
        scanf("%d", &team);
        if (team == 1) {
            c[S][i] = INF;
            adj[S].push_back(i);
            adj[i].push_back(S);
        } else if (team == 2) {
            c[i][E] = INF;
            adj[i].push_back(E);
            adj[E].push_back(i);
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int capacity;
            scanf("%d", &capacity);
            if (i != j) {
                c[i][j] = capacity;
                if (capacity > 0) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
    }

    // 디닉 알고리즘 수행: 최대 유량 계산
    int total = 0;
    level.assign(N + 2, -1);
    work.assign(N + 2, 0);

    while (bfs()) {
        fill(work.begin(), work.end(), 0);
        while (int flow = dfs(S, E, INF)) {
            total += flow;
        }
    }
    printf("%d\n", total);

    // 소스에서 도달 가능한 노드 찾기
    vector<bool> visited(N + 2, false);
    queue<int> Q;
    visited[S] = true;
    Q.push(S);
    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();
        for (int next : adj[curr]) {
            if (!visited[next] && c[curr][next] - f[curr][next] > 0) {
                visited[next] = true;
                Q.push(next);
            }
        }
    }

    // 결과 출력: A진영과 B진영 구분
    for (int i = 0; i < N; i++)
        if (visited[i]) printf("%d ", i + 1);
    puts("");
    for (int i = 0; i < N; i++)
        if (!visited[i]) printf("%d ", i + 1);
    puts("");

    return 0;
}