【网络流】——搞搞dinic

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int inf=1e9;
 7 const int N=1e6+10;
 8 int n,m,S,T,cnt=-1,maxflow,head[N],cur[N],deep[N];
 9 queue<int> q;
10 struct edge{
11     int to,next,w;
12 }e[N*2];
13 void addedge(int from,int to,int w){
14     e[++cnt]=(edge){to,head[from],w};
15     head[from]=cnt;
16 }
17 int bfs(int s,int t){//将图分层。 
18     for(int i=1;i<=n;i++) deep[i]=1e9+10;
19     while(!q.empty()) q.pop();
20     for(int i=1;i<=n;i++) cur[i]=head[i];
21     deep[s]=0;
22     q.push(s);
23     while(!q.empty()){
24         int u=q.front();
25         q.pop();
26         for(int i=head[u];i!=-1;i=e[i].next){
27             int v=e[i].to;
28             if(deep[v]>inf&&e[i].w){
29                 deep[v]=deep[u]+1;
30                 q.push(v);
31             }
32         }
33     }
34     if(deep[t]<inf) return true;
35     else return false;
36 }
37 int dfs(int u,int t,int lim){//lim=minedge(s->u) 
38     if(!lim||u==t) return lim;//如果到了汇点或者边权为0则返回边权。
39     int flow=0,f;
40     for(int i=cur[u];i!=-1;i=e[i].next){
41         cur[u]=i;//弧优化
42         int v=e[i].to;
43         if(deep[v]==deep[u]+1&&(f=dfs(v,t,min(lim,e[i].w)))){//如果这段能到达汇点并且服从分层 
44             flow+=f;
45             lim-=f;
46             e[i].w-=f;
47             e[i^1].w+=f;
48             if(!lim) break;
49         }
50     }
51     return flow;
52 }//important
53 void dinic(int s,int t){
54     while(bfs(s,t)){
55         maxflow+=dfs(s,t,inf);
56     }
57 }
58 int main(){
59     scanf("%d%d%d%d",&n,&m,&S,&T);
60     int x,y,z;
61     memset(head,-1,sizeof(head));
62     for(int i=1;i<=m;i++){
63         scanf("%d%d%d",&x,&y,&z);
64         addedge(x,y,z);
65         addedge(y,x,0);
66     }
67     dinic(S,T);
68     printf("%d",maxflow);
69     return 0;
70 }