Dinic 算法

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N (1e5+5), M(1e5+5);
 5 
 6 int head[N];
 7 struct Edge{
 8     /*
 9     r: residual capacity
10     */
11     int v, r, nt;
12 }E[M];
13 int tail;
14 void add_edge(int u, int v, int c){
15     E[tail]={v, c, head[u]}, head[u]=tail++;
16     E[tail]={u, 0, head[v]}, head[v]=tail++;
17 }
18 
19 int level[N];
20 void bfs(int s){
21     memset(level, -1, sizeof(level));
22     queue<int> que;
23     level[s]=0;
24     que.push(s);
25     for(int u; !que.empty(); ){
26         u=que.front(), que.pop();
27         for(int i=head[u]; ~i; i=E[i].nt){
28             int &v=E[i].v;
29             if(E[i].r>0 && level[v]<0){
30                 level[v]=level[u]+1;
31                 que.push(v);
32             }
33         }
34     }
35 }
36 
37 int iter[N];
38 int dfs(int u, int t, int f){
39     /*
40     t: terminal (sink)
41     */
42     if(u==t) return f;
43     //for(int &i=iter[u]; i!=-1; i++){
44     for(int &i=iter[u]; i!=-1; i=E[i].nt){
45         int &v=E[i].v, &r=E[i].r;
46         if(r>0 && level[u]<level[v]){
47             int d=dfs(v, t, min(f, r));
48             if(d>0){
49                 r-=d;
50                 E[i^1].r+=d;
51                 return d;
52             }
53         }
54     }
55     return 0;
56 }
57 
58 int dinic(int s, int t){
59     const int INF=1<<30;
60     for(int flow=0;;){
61         bfs(s);
62         if(level[t]<0) return flow;
63         memcpy(iter, head, sizeof(iter));
64         for(int f; f=dfs(s, t, INF); flow+=f);
65     } 
66 }
67 
68 void init(){
69     tail=0;
70     memset(head, -1, sizeof(head));
71 }