其实很多大佬已经写得极好了我就放几篇链接就算了：
1：https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-di-zong-jie
2：https://www.cnblogs.com/LUO77/p/6115057.html
3：https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic
4：https://www.luogu.org/blog/xht37/er-fen-tu-yu-wang-lao-liu
5：http://blog.csdn.net/A_Comme_Amour/article/details/79356220
但是还是放一下我的代码毕竟大佬很多代码注释让人云里雾里但蒟蒻我很懂你（以下放置EK和Dinic的代码）
EK算法
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,s,t; 4 const int MAXN=2e6+10; 5 const int INF=1e9+10; 6 struct edge{ 7 int u,v,flow/*这条道路还有的容量*/,nxt; 8 }e[MAXN]; //用邻接表存图 9 int tot; 10 int first[MAXN]; 11 int path[MAXN];/*因为增广路一定是一条链，所以用这个数组记录来的方式*/ 12 int a[MAXN]; /*记录到a[i]时路径中的容量最小值*/ 13 inline void add_edge(int x,int y,int z) 14 { 15 e[tot].u=x; 16 e[tot].v=y; 17 e[tot].flow=z; 18 e[tot].nxt=first[x]; 19 first[x]=tot++;/*因为本人过菜，从0开始存边*/ 20 } 21 inline int EK() 22 { 23 int ans=0; 24 while(true)/*不断更新增广路*/ 25 { 26 //开始一次用bfs找一次增广路 27 memset(a,0,sizeof(a)); 28 queue<int>q; 29 q.push(s); 30 a[s]=INF; 31 while(q.size()!=0) 32 { 33 int p=q.front(); 34 q.pop(); 35 for(int i=first[p];i!=-1;i=e[i].nxt) 36 { 37 if(a[e[i].v]==0&&e[i].flow!=0) 38 { 39 path[e[i].v]=i; //记录路径 40 a[e[i].v]=min(a[p],e[i].flow);//记录这个增广路上的最小容量 41 q.push(e[i].v); 42 } 43 } 44 if(a[t])break;//如果已经找到了一条路径就可以退出扩展了 45 } 46 if(!a[t])break;//但如果直到最后都再也走不到我们可爱的终点了，拜拜 47 for(int i=t;i!=s;i=e[path[i]].u)//用自己先前保存的路径更新 48 { 49 e[path[i]].flow-=a[t]; //当前边的容量减去本次更新的值 50 e[path[i]^1].flow+=a[t];//将这条边的反边容量加上这次更新的值 51 } 52 ans+=a[t];//答案加上本次扩展结果 53 } 54 return ans;//返回***** 55 } 56 int main() 57 { 58 memset(first,-1,sizeof(first));/*因为是从0开始存的边所以要将first这个存第一个边的编号的数组赋为-1*/ 59 scanf("%d %d %d %d",&n,&m,&s,&t); 60 for(register int i=1;i<=m;i++) 61 { 62 int x,y,z; 63 scanf("%d %d %d",&x,&y,&z); 64 add_edge(x,y,z); 65 add_edge(y,x,0);/*在加边的同时将反边加上*/ 66 } 67 printf("%d",EK()); 68 return 0; 69 }
Dinic算法（未优化，等待更新）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int dep[10009]/*记录第几层被搜到避免自己对自己流入*/,first[10009]; 4 bool inque[10009];//在下面用bfs找增广路时记录是否在队列当中 5 int tot=0; 6 int n,m,s,t; 7 const int inf=1<<30; 8 struct edge{ 9 int to; 10 int val; 11 int nxt; 12 }e[200109]; 13 inline int kd(){ 14 int x=0;char c=getchar(); 15 while(c>'9'||c<'0')c=getchar(); 16 while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); 17 return x; 18 } 19 inline void add_edge(int a,int b,int c) 20 { 21 e[tot].to=b; 22 e[tot].val=c; 23 e[tot].nxt=first[a]; 24 first[a]=tot; 25 tot++;/*毕竟和上篇一样时从零开始的异世界*/ 26 } 27 bool bfs()/*寻找增广路*/ 28 { 29 memset(dep,0x3f3f3f3f,sizeof(dep));/*赋值*/ 30 memset(inque,false,sizeof(inque));/*清空之境界*/ 31 dep[s]=0; 32 queue<int>q; 33 q.push(s); 34 while(q.empty()==false) 35 { 36 int now=q.front(); 37 q.pop(); 38 inque[now]=false; 39 for(int i=first[now];i!=-1;i=e[i].nxt) 40 { 41 int to=e[i].to; 42 if(dep[to]>dep[now]+1&&e[i].val!=0/*保证不是已经一滴都不剩的边*/)/*如果to的层数更深那就流向它*/ 43 { 44 dep[to]=dep[now]+1; 45 if(inque[to]==false) 46 { 47 q.push(to); 48 inque[to]=true; 49 } 50 } 51 } 52 } 53 if(dep[t]!=0x3f3f3f3f)return true; 54 return false;/*如果最后一个点根本流不到它就凉了*/ 55 } 56 int dfsl(int now,int flow) 57 { 58 int rlow=0;/*用于保存当前答案*/ 59 if(now==t)return flow;/*已经流到终点就回溯*/ 60 for(int i=first[now];i!=-1/*因为从零开始当然不能是-1啦---02*/;i=e[i].nxt) 61 { 62 int to=e[i].to; 63 if(e[i].val!=0&&dep[now]+1==dep[to])/*如果可以走*/ 64 { 65 if(rlow=dfsl(to,min(flow,e[i].val)/*进一步求出扩展值*/)) 66 { 67 e[i].val-=rlow; 68 e[i^1].val+=rlow; 69 return rlow;/*同上一篇EK算法*/ 70 } 71 } 72 } 73 return 0; 74 } 75 int dinic() 76 { 77 int lowflow; 78 int maxflow=0; 79 while(bfs()) 80 { 81 while(lowflow=dfsl(s,inf)) 82 { 83 maxflow+=lowflow;/*答案更新本次扩展值*/ 84 } 85 } 86 return maxflow; 87 } 88 int main() 89 { 90 memset(first,-1,sizeof(first)); 91 n=kd(),m=kd(),s=kd(),t=kd(); 92 for(int i=1;i<=m;i++) 93 { 94 int a=kd(),b=kd(),c=kd(); 95 add_edge(a,b,c); 96 add_edge(b,a,0); 97 } 98 int sum=0; 99 printf("%d ",dinic()); 100 return 0; 101 }
Dinic当前弧优化（跑得快到飞起）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,s,t; 4 int vis; 5 int dep[100009]; 6 int inque[1000009]; 7 int cur[1000009]; 8 int maxflow=0; 9 struct edge{ 10 int to,nxt,flow; 11 }e[200009];int tot=-1; 12 int first[100009]; 13 const int inf=0x3f3f3f3f; 14 inline int kd() 15 { 16 int x=0,f=1;char ch=getchar(); 17 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 18 while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();} 19 return x*f; 20 } 21 inline void add_edge(int a,int b,int c) 22 { 23 e[++tot].to=b; 24 e[tot].flow=c; 25 e[tot].nxt=first[a]; 26 first[a]=tot; 27 } 28 bool bfs() 29 { 30 for(register int i=0;i<=n;i++)cur[i]=first[i]/*在这里把cur赋值*/,inque[i]=false,dep[i]=0x3f3f3f3f; 31 dep[s]=0; 32 queue<int>q; 33 q.push(s); 34 while(q.empty()==false) 35 { 36 int now=q.front(); 37 q.pop(); 38 inque[now]=false; 39 for(int i=first[now];i!=-1;i=e[i].nxt) 40 { 41 int to=e[i].to; 42 if(dep[now]+1<dep[to]&&e[i].flow!=0) 43 { 44 dep[to]=dep[now]+1; 45 if(inque[to]==false) 46 { 47 inque[to]=true; 48 q.push(to); 49 } 50 } 51 } 52 } 53 if(dep[t]==0x3f3f3f3f)return false; 54 return true; 55 } 56 int dfsl(int now,int nowflow) 57 { 58 int rlow=0; 59 if(now==t)return nowflow; 60 for(int i=cur[now]/*这样就直接跳走了*/;i!=-1;i=e[i].nxt) 61 { 62 cur[now]=i;/*这样可以跳过中间走过的点可以减少走的次数*/ 63 if(dep[now]+1==dep[e[i].to]&&e[i].flow!=0) 64 { 65 if(rlow=dfsl(e[i].to,min(nowflow,e[i].flow))) 66 { 67 e[i].flow-=rlow; 68 e[i^1].flow+=rlow; 69 return rlow; 70 } 71 } 72 } 73 return 0; 74 } 75 int dinic() 76 { 77 int lowflow; 78 while(bfs()) 79 { 80 while(lowflow=dfsl(s,inf)) 81 { 82 maxflow+=lowflow; 83 } 84 } 85 } 86 int main() 87 { 88 memset(first,-1,sizeof(first)); 89 n=kd(),m=kd(),s=kd(),t=kd(); 90 for(int i=1;i<=m;i++) 91 { 92 int a=kd(),b=kd(),c=kd(); 93 add_edge(a,b,c); 94 add_edge(b,a,0); 95 } 96 dinic(); 97 cout<<maxflow<<endl; 98 }
