Dinic's algorithm

최대 유량 알고리즘의 최종 버전.

구현은 충분히 외울 수 있을 정도로 직관적이다.

시간복잡도: O(V^2E) (라고 하지만 더 빠르다.)

 

13161번: 분단의 슬픔

 

#include<bits/stdc++.h>
using namespace std;
const int V=503;
const int s=501;
const int t=502;
const int INF=2e9;
int n;
int c[V][V],f[V][V];
vector<int> ad[V];
int lev[V],work[V];
bool chk[V];
bool bfs()
{
    memset(lev,-1,sizeof lev);
    queue<int> q; q.push(s);
    lev[s]=0;
    while(!q.empty()){
        int cur=q.front(); q.pop();
        for(int nxt : ad[cur]){
            if(lev[nxt]==-1&&c[cur][nxt]-f[cur][nxt]>0){
                lev[nxt]=lev[cur]+1;
                q.push(nxt);
            }
        }
    }
    return ~lev[t];
}
int dfs(int cur,int tot)
{
    if(cur==t) return tot;
    for(int &i=work[cur];i<ad[cur].size();i++){
        int nxt=ad[cur][i];
        if(lev[nxt]==lev[cur]+1&&c[cur][nxt]-f[cur][nxt]>0){
            int flow=dfs(nxt,min(tot,c[cur][nxt]-f[cur][nxt]));
            if(flow>0){
                f[cur][nxt]+=flow;
                f[nxt][cur]-=flow;
                return flow;
            }
        }
    }
    return 0;
}
void decom()
{
    queue<int> q; q.push(s);
    chk[s]=true;
    while(!q.empty()){
        int cur=q.front(); q.pop();
        for(int nxt : ad[cur]){
            if(!chk[nxt]&&c[cur][nxt]-f[cur][nxt]>0){
                chk[nxt]=1;
                q.push(nxt);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x==1){
            c[s][i]=INF;
            ad[s].push_back(i);
            ad[i].push_back(s);
        }
        if(x==2){
            c[i][t]=INF;
            ad[i].push_back(t);
            ad[t].push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&c[i][j]);
            if(i!=j) ad[i].push_back(j);
        }
    int ans=0;
    while(bfs()){
        memset(work,0,sizeof work);
        while(1){
            int flow=dfs(s,INF);
            if(!flow) break;
            ans+=flow;
        }
    }
    printf("%d\n",ans);
    decom();
    vector<int> a,b;
    for(int i=1;i<=n;i++){
        if(chk[i]) a.push_back(i);
        else b.push_back(i);
    }
    for(int i : a) printf("%d ",i);
    puts("");
    for(int i : b) printf("%d ",i);
    puts("");
}

 

JusticeHui님의 코드를 적극 참고하였습니다.