OI

【模板】Dinic最大流

码完30分钟，Debug四小时（哭）

一、Ford-Fulkerson

利用残余网络和搜索时建立反向边实现不断增广，一遍遍bfs直到结束。除了建边的操作之外基本与bfs相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cstdlib>
#include<memory.h>
#include<queue>
using namespace std;
const int MAXN=205;
const int MAXM=205;
const int inf=214783647;
int n,m,source=1,sink,u,v,w,ans;
int map[MAXM][MAXM]={0};

struct node{
    int min;
    int no;
};

int bfs(){
    int vis[MAXN]={0};
    queue<node> q;
    int l[MAXM];
    node t,now;
    int i,j1,j2;
    t.no=source;
    t.min=inf;
    q.push(t);
    l[t.no]=-1;
    vis[t.no]=1;
    do{
        now=q.front();
        q.pop();
        for(i=1;i<=m;i++){
            if(map[now.no][i]!=0&&!vis[i]){
                t.no=i;
                if(now.min>map[now.no][i])
                    t.min=map[now.no][i];
                else t.min=now.min;
                q.push(t);
                l[t.no]=now.no;
                vis[t.no]=1;
                if(t.no==sink){
                    j2=t.no;
                    j1=t.no;
                    while(j1!=-1){
                        j1=l[j1];
                        
                        
                        map[j1][j2]-=t.min;
                        map[j2][j1]+=t.min;
                        
                        j2=j1;
                    }
                    ans+=t.min;
                    return 1;
                }
            }
        }
    }while(!q.empty());
    return 0;
}

void so(){
    while(bfs());
}

int main(){
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(map,0,sizeof(map));
        ans=0;
        sink=m;
        
        for(i=1;i<=n;i++){
            scanf("%d%d%d",&u,&v,&w);
            map[u][v]+=w;
        }
        so();
        printf("%d\n",ans);
        
    }
    return 0;
}

二、Dinic

在Ford-Fulkerson的基础上，减少冗余的搜索，所进行的优化。总的思想是将图分层，先bfs决定路径层次，再dfs找增广路，直到无增广路。
这次又使用了邻接表的形式进行优化，其中学到了一个厉害的操作：
在增广时，需要建立反向边，邻接矩阵中map[i][j]的反向边即map[j][i]，十分便捷。
然而，在邻接表中，每一条边是分散储存没有规律的，那怎么解决反向的问题呢？
这里用到一种方法：在建图时，每建一条边就紧接着建立一条反向边。此时，在数组模拟邻接表中，两边的下标是连续的。然后，我们规定邻接表数组从0开始，这样建立的边就被分为：(0,1),(2,3),(4,5)…
这样，两下标之间的关系竟可以表示为(i,i^1)！
//高位xor0不变，低位xor1变反，刚好差1
如此便实现了邻接表建立反向边的操作。
（不禁让我感叹到底是谁发现的数组模拟邻接表，这利用数组下标的关系直接访问的操作连链表邻接表都无法实现啊）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<memory.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=2005;
const int MAXM=2005;
const int inf=2147483647;
int n,m,x,y,z,sink,source,ans,depth[MAXN];
struct EDGE{
    int next;
    int to;
    int weight;
};
EDGE graph[MAXM];
int head[MAXN]={0},nume=-1;

void adde(int f,int t,int w){
    graph[++nume].next=head[f];
    graph[nume].to=t;
    graph[nume].weight=w;
    head[f]=nume;
}

int bfs(){
    memset(depth,0,sizeof(depth));
    queue<int> q;
    int now;
    int i;
    while(!q.empty())
        q.pop();
    q.push(source);
    depth[source]=1;
    do{
        now=q.front();
        q.pop();
        for(i=head[now];i!=-1;i=graph[i].next){
            if(graph[i].weight!=0&&depth[graph[i].to]==0){
                depth[graph[i].to]=depth[now]+1;
                q.push(graph[i].to);
            }
        }
    }while(!q.empty());
    if(depth[sink]==0)return 0;
    return 1;
}

int dfs(int i,int m){
    int j,t;
    if(i==sink)
        return m;
    for(j=head[i];j!=-1;j=graph[j].next)
        if((depth[graph[j].to]==depth[i]+1)
        &&graph[j].weight!=0){
            
            t=dfs(graph[j].to,min(m,graph[j].weight));
            if(t>0){
                graph[j].weight-=t;
                graph[j^1].weight+=t;
                return t;
            }
        }
    
    return 0;
}

void dinic(){
    int t;
    while(bfs())
        while(t=dfs(source,inf))
            ans+=t;
}

int main(){
    int i;
    while(scanf("%d%d",&m,&n)!=EOF){
    	memset(head,-1,sizeof(head));
        nume=-1;
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            adde(x,y,z);
            adde(y,x,0);
        }
        
        source=1;
        sink=n;
        ans=0;
        
        
        dinic();
        printf("%d\n",ans);
    }
    
    return 0;
}

另外，Dinic的当前弧优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<memory.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=40005;
const int MAXM=400005;
const int inf=2147483647;
int n,m,n1,n2,n3,m1,m2,x,y,T,S,ans,dep[MAXN];
struct EDGE{
    int next;
    int to;
    int w;
};
EDGE g[MAXM*2];
int head[MAXN]={0},cur[MAXN],nume=-1;

inline void adde(int f,int t,int w){
    g[++nume].next=head[f];
    g[nume].to=t;
    g[nume].w=w;
    head[f]=nume;
}

inline int bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;
    int now;
    int i;
    while(!q.empty())
        q.pop();
    q.push(S);
    dep[S]=1;
    do{
        now=q.front();
        q.pop();
        for(i=head[now];i!=-1;i=g[i].next)
            if(g[i].w!=0&&dep[g[i].to]==0){
                dep[g[i].to]=dep[now]+1;
                q.push(g[i].to);
            }
    }while(!q.empty());
    if(dep[T]==0)return 0;
    return 1;
}

int dfs(int i,int m){
    int t;
    if(i==T)
        return m;
    for(int& j=cur[i];j!=-1;j=g[j].next)
        if((dep[g[j].to]==dep[i]+1)&&g[j].w!=0){
            
            t=dfs(g[j].to,min(m,g[j].w));
            if(t>0){
                g[j].w-=t;
                g[j^1].w+=t;
                return t;
            }
        }
    
    return 0;
}

inline void dinic(){
    int t,i;
    while(bfs()){
        for (i=1;i<=n;i++)
            cur[i]=head[i];
        while(t=dfs(S,inf))
            ans+=t;
        
    }
}

这里的dfs中的j的引用类型和C中的指针写法是一致的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dfs(int i,int m){
    int t;
    int *j;
    if(i==T)
        return m;
    for(j=&cur[i];*j!=-1;*j=g[*j].next)
        if((dep[g[*j].to]==dep[i]+1)&&g[*j].w!=0){
            
            t=dfs(g[*j].to,min(m,g[*j].w));
            if(t>0){
                g[*j].w-=t;
                g[*j^1].w+=t;
                return t;
            }
        }
    
    return 0;
}