Dinic模板

 1 struct Edge
 2 {
 3     int from,to,cap,flow;
 4     Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){}
 5 };
 6 
 7 struct Dinic
 8 {
 9     int n,m,s,t;
10     vector<Edge> edges;
11     vector<int> G[maxn];
12     bool vis[maxn];
13     int cur[maxn];
14     int d[maxn];
15 
16     void init(int n)
17     {
18         this->n=n;
19         for(int i=0;i<n;++i) G[i].clear();
20         edges.clear();
21     }
22 
23     void AddEdge(int from,int to,int cap)
24     {
25         edges.push_back( Edge(from,to,cap,0) );
26         edges.push_back( Edge(to,from,0,0) );
27         m=edges.size();
28         G[from].push_back(m-2);
29         G[to].push_back(m-1);
30     }
31 
32     bool BFS()
33     {
34         queue<int> Q;
35         memset(vis,0,sizeof(vis));
36         vis[s]=true;
37         d[s]=0;
38         Q.push(s);
39         while(!Q.empty())
40         {
41             int x=Q.front(); Q.pop();
42             for(int i=0;i<G[x].size();++i)
43             {
44                 Edge& e=edges[G[x][i]];
45                 if(!vis[e.to] && e.cap>e.flow)
46                 {
47                     vis[e.to]=true;
48                     d[e.to]=d[x]+1;
49                     Q.push(e.to);
50                 }
51             }
52         }
53         return vis[t];
54     }
55 
56     int DFS(int x,int a)
57     {
58         if(x==t || a==0) return a;
59         int flow=0, f;
60         for(int &i=cur[x];i<G[x].size();++i)
61         {
62             Edge &e=edges[G[x][i]];
63             if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0)
64             {
65                 e.flow +=f;
66                 edges[G[x][i]^1].flow -=f;
67                 flow +=f;
68                 a -=f;
69                 if(a==0) break;
70             }
71         }
72         return flow;
73     }
74 
75     int Maxflow(int s,int t)
76     {
77         this->s=s; this->t=t;
78         int flow=0;
79         while(BFS())
80         {
81             memset(cur,0,sizeof(cur));
82             flow +=DFS(s,INF);
83         }
84         return flow;
85     }
86 }DC;