Dinic - Network Flow (Maximum Flow)

오늘 드디어 디닉 알고리즘을 정복했다.

작년 입사시험 보기전에

서티 기출로 네트워크 플로우 문제가 나왔다고 해서

디닉까지 준비해서 가려고 했었는데,

그때부터 지금까지 준비한다고 말만하다가 1년도 더 지난 오늘에서야 공부하게 됐다 ㅠ

시간복잡도는 O(V^2 E)이지만 이것보다 훨씬 빨리 동작하며, 거의 O(VE)로 봐도 무방할만큼의 속도를 보여준다.

사실상 PS문제에서 Network Flow문제가 제한에 대해 최악의 경우까지 가도록 테케를 만드는건 거의 불가능(?)하기 때문에...

아무튼 생각보다 훨씬 쉬웠다.

역시 지금까지 공부한 알고리즘 중에서 LCP가 제일 익히기 까다로웠는데,

그에 비하면 디닉은 아주 쉬웠다.

간단하게 말하자면 bfs돌면서 정점들의 level을 체크해주고,

level체크가 완료되면 network flow를 dfs로 구현하는 방식을 그대로 사용해서 flow를 흘려주면 된다.

다만 여기서 한번 봤던 간선을 다시 보지 않는 것이 매우매우 중요하다.

(여기서 Edmonds-Karp Algorithm과 큰 차이가 나게 된다.)

코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int r[502][502];
bool chk[502][502];
vector<int> v[502];
const int inf = 0x3f3f3f3f;
queue<int> q;
int level[502];
bool bfs(int src, int sink) {
    memset(level,-1,sizeof(level));
    level[src]=0;
    q.push(src);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int y: v[x]) {
            if(r[x][y]>0 && level[y]<0) {
                level[y]=level[x]+1;
                q.push(y);
            }
        }
    }
    return level[sink]>=0;
}
int work[502];
int dfs(int x, int sink, int f) {
    if(x==sink) return f;
    for(int &i=work[x]; i<v[x].size(); i++) {
        int y=v[x][i];
        if(level[y]>level[x] && r[x][y]>0) {
            int t = dfs(y,sink,min(f,r[x][y]));
            if(t>0) {
                r[x][y]-=t;
                r[y][x]+=t;
                return t;
            }
        }
    }
    return 0;
}
int dinic(int src, int sink) {
    int flow=0;
    while(bfs(src,sink)) {
        int f=0;
        memset(work,0,sizeof(work));
        while((f=dfs(src,sink,inf))>0) flow+=f;
    }
    return flow;
}

방금전에 제일 중요하다고 언급했던 부분이 31번째 줄에서 work[x]를 레퍼런스 i로 받은 것이다.

네트워크 플로우 알고리즘을 이미 알고 있다면, 위의 설명과 코드만 보고도 쉽게 이해할 수 있을 것이다.

디닉으로만 풀리는 문제는 BOJ 13161 문제가 있다.

나는 이 알고리즘을 노란책(프로그래밍 콘테스트 챌린징)과 kks227님의 블로그(http://kks227.blog.me/220812858041)에서 참고했다.

BOJ 13161 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int r[502][502];
bool chk[502][502];
vector<int> v[502];
const int inf = 0x3f3f3f3f;
void mkedge(int x, int y, int w) {
    if(!chk[x][y]) {
        v[x].push_back(y);
        v[y].push_back(x);
    }
    chk[x][y]=chk[y][x]=true;
    r[x][y]+=w;
}
queue<int> q;
int level[502];
bool bfs(int src, int sink) {
    memset(level,-1,sizeof(level));
    level[src]=0;
    q.push(src);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int y: v[x]) {
            if(r[x][y]>0 && level[y]<0) {
                level[y]=level[x]+1;
                q.push(y);
            }
        }
    }
    return level[sink]>=0;
}
int work[502];
int dfs(int x, int sink, int f) {
    if(x==sink) return f;
    for(int &i=work[x]; i<v[x].size(); i++) {
        int y=v[x][i];
        if(level[y]>level[x] && r[x][y]>0) {
            int t = dfs(y,sink,min(f,r[x][y]));
            if(t>0) {
                r[x][y]-=t;
                r[y][x]+=t;
                return t;
            }
        }
    }
    return 0;
}
int dinic(int src, int sink) {
    int flow=0;
    while(bfs(src,sink)) {
        int f=0;
        memset(work,0,sizeof(work));
        while((f=dfs(src,sink,inf))>0) flow+=f;
    }
    return flow;
}
int main() {
    int n; scanf("%d", &n);
    int src=0, sink=n+1;
    for(int i=1; i<=n; i++) {
        int t; scanf("%d", &t);
        if(t==1) mkedge(src,i,inf);
        else if(t==2) mkedge(i,sink,inf);
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            int c; scanf("%d", &c);
            if(i==j) continue;
            mkedge(i,j,c);
        }
    }
    printf("%d\n", dinic(src,sink));
    for(int i=1; i<=n; i++) if(level[i]>=0) printf("%d ",i); puts("");
    for(int i=1; i<=n; i++) if(level[i]<0) printf("%d ", i); puts("");
    return 0;
}
 

끄읕~