网络流模板

 1 const int maxn = 1e5+7;
 2 const int INF  = 1<<30;
 3 const int mod  = 1e9+7;
 4 struct Edge{
 5      int from,to,cap,flow;
 6 };
 7 
 8 struct Dinic
 9 {
10     int n,m,s,t;
11     vector<Edge>edge;
12     vector<int>G[maxn];
13     bool vis[maxn];
14     int d[maxn];
15     int cur[maxn];
16     void init(int n){
17         this->n = n;
18         for(int i=0;i<=n;i++)G[i].clear(),edge.clear();
19     }
20     inline void addedge(int from,int to,int cap){
21         edge.pb((Edge){from,to,cap,0});
22         edge.pb((Edge){to,from,0,0});
23         m = edge.size();
24         G[from].pb(m-2);
25         G[to].pb(m-1);
26     }
27     inline bool bfs(){
28         mem(vis,0);
29         queue<int>Q;
30         Q.push(s);
31         d[s] = 0;
32         vis[s] = 1;
33         while(!Q.empty()){
34             int x = Q.front(); Q.pop();
35             int sz = G[x].size();
36             for(int i=0;i<sz;++i){
37                 Edge &e = edge[G[x][i]];
38                 if(!vis[e.to] && e.cap>e.flow){
39                     vis[e.to] = 1 ;
40                     d[e.to] = d[x] + 1;
41                     Q.push(e.to); 
42                 }
43             }
44         }
45         return vis[t];
46     }
47     int dfs(int x,int a){
48         if(x == t || a == 0)return a;
49         int flow = 0,f;
50         int sz = G[x].size();
51         for(int &i = cur[x];i<sz;i++){
52             Edge &e = edge[G[x][i]];
53             if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow)))>0){
54                 e.flow += f;
55                 edge[G[x][i]^1].flow -=f;
56                 flow += f;
57                 a -= f;
58                 if(a==0)break;
59             }
60         }
61         //if(!flow) d[x] = -2;  //炸点优化
62         return flow;
63     }
64     inline int maxflow(int s,int t){
65         this->s = s; this -> t = t;
66         int flow = 0;
67         while(bfs()){
68             mem(cur,0);
69             flow += dfs(s,INF);
70         }
71         return flow;
72     }
73 };