本人很弱，只会Dinic、EK与Ford-Fulkerson...(正在学习ISAP...)
这里讲Dinic...
Dinic:与Ford-Fulkerson和的思路相似（话说好像最大流求解都差不多吧），也是使用深搜寻找增广路（至于增广路是什么，只要在学最大流而不是借鉴他人代码的应该都知道吧）。
但是（划重点），Dinic有一个十分不一样的地方（Dinic：我们不一样，不一样！），就是还用了**BFS**（是为了凑齐深搜广搜召唤神龙）！
BFS有什么用呢，除了使时间复杂度更上一层楼之外，还有什么用呢？
这就是Dinic的神奇之处了，BFS反而使时间复杂度降低，与EK看似肩并肩（EK：O(nm^2) Dinic:O(n^2m)）。看上去是肩并肩了，实则在题目上，Dinic基本都比EK优秀，特别是二分图。
扯远了，继续讲Dinic的BFS的用处。
BFS是为了划分等级（周朝的分封制！），使得在找增广路时跳过一些对这条增广路没用的点，使DFS效率大大提高。
另外，代码还可以加上当前弧优化与多路增广使其更快。
多路增广，设置一个变量used，记录这条边的流量，就不用搜到就退了，最后满了再退出。
当前弧优化：设置一个数组，在BFS预处理中将它赋值head[i]，就相当于邻接表里的head，但是（划重点）它的值是随着增广的时候所变小的，然后下次增广时就可以跳过已经用过的边。
献上我丑陋的代码：
#include<cstdio> #define INF 0x3f3f3f3f #define maxn 3000001 inline int read(){//快读 int r=0,f=1; char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1; c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ r=r*10+c-‘0‘; c=getchar(); } return r*f; } void write(int x)//快速输出 { if(x<0) putchar(‘-‘),x=-x; if(x>9) write(x/10); putchar(x%10+‘0‘); } struct edge{ int v,c,nxt; }e[2*maxn]; //struct max_Fow{//本来写了结构体的 int S,T,N,head[maxn],q[maxn],cur[maxn],level[maxn],tot=0,hd,tl,v; inline void init(int s,int t,int n){//为结构体而写 S=s; T=t; N=n+1; for(register int i=1;i<N;i++)//想想为什么不直接为0 head[i]=-1; } inline void add_edge(int u,int v,int c){ e[tot]=(edge){v,c,head[u]};//为什么从0开始？ head[u]=tot++; } inline void add(int u,int v,int c){ add_edge(u,v,c); add_edge(v,u,0);//反向边 } inline bool BFS(){ for(register int i=1;i<N;i++){ cur[i]=head[i];//当前弧优化初始化 level[i]=0;//等级初始化 } q[1]=S; level[S]=1; hd=0;tl=1; while(hd^tl){//广搜 hd++; for(register int i=head[q[hd]];i!=-1;i=e[i].nxt){ if(e[i].c&&!level[e[i].v]){ tl++; level[e[i].v]=level[q[hd]]+1; q[tl]=e[i].v; if(e[i].v==T)return true;//搜到就退 } } } return false;//否则无法拓展到汇点 } inline int min(int a,int b){//手写min if(a<b)return a; return b; } int DFS(int f,int u){ if(u==T)return f; int d=0,used=0;//多路增广 for(int &i=cur[u];i!=-1;i=e[i].nxt){//当前弧优化 if(e[i].c&&level[u]==level[e[i].v]-1){ if((d=DFS(min(f-used,e[i].c),e[i].v))){ e[i].c-=d; e[i^1].c+=d;//为什么可以直接这样？ used+=d;//多路增广 } } } if(!used)level[u]=0; return used; } inline int Dinic(){//求解 int max_flow=0; while(BFS()){ int d=0; while((d=DFS(INF,S))) max_flow+=d; } return max_flow; } //}Flow; int main(){ int n=read(),m=read(),s=read(),t=read(),i; /*Flow.*/init(s,t,n); for(i=1;i<=m;i++){ int a=read(),b=read(),v=read(); /*Flow.*/add(a,b,v); } int ans=/*Flow.*/Dinic(); write(ans); return 0; }
Q:为什么head[]初始值为-1更好？
A:因为开始值就会为0，xor1就等于+1或-1，那样又会少了一些判断，
并且，Dinic也可以做费用流，只要将广搜换为SPFA就行了
完结撒花！！！??ヽ(°▽°)ノ?
原文：https://www.cnblogs.com/wyzwyz/p/10858982.html