@[网络流——最大流——Dinic算法的初步认识]
！！！！！！！目前博客转移 https://www.cnblogs.com/everlasting-k/p/13777489.html !!!
简单说一说：有一个起点（源点），和一个终点（汇点），它们之间用很多直径大小不一的管子连在一起，为什么要用大小不一的管子，（假如这些都是水管），那么你要做的就是：算出从源点到汇点最大可以流入多少水。
显然，对于一条路上，它的最大流是这条路上直径最小的管子所能承受的水量（再多的话，那最小的水管就爆了）。 于是乎，直径最小的水管就被占满了——不能再有更多的水从这里通过，而直径比它大的管子还没被占满——所以他们还可以再让更多的水通过。
大概就这么个意思_如下图 最后，把所有到达汇点的水量加起来就行了。
直接上代码！！！
#include<bits/stdc++.h> using namespace std; const int INF=0xfffffff; const int MAXN=5200199; int s,t,n,m; int tot=1; int first[MAXN]; int dep[MAXN]; struct node{ int from,to,v; int next; }; node edge[MAXN*2]; void add(int u,int v,int w) { tot++; edge[tot].from=u; edge[tot].to=v; edge[tot].v=w; edge[tot].next=first[u]; first[u]=tot; } bool bfs() //建立分层图，每次dfs就是在最新的分层图的基础上进行的 { memset(dep,-1,sizeof(dep)); dep[s]=0; queue<int> q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=first[u];i;i=edge[i].next) { int j=edge[i].to; if(dep[j]==-1 && edge[i].v) { dep[j]=dep[u]+1; q.push(j); } } } return dep[t]!=-1; } int dfs(int u,int flow) //以u记录当前编号，flow记录目前的最大流 { if(u==t) { return flow; } int delta=flow; // ！！重点，以delta记录 向下传递的最大流 与 实际接收的最大流 的差。 -->其实就是INF与最后答案的差 for(int i=first[u];i;i=edge[i].next) { int to=edge[i].to; int w=edge[i].v; if((dep[to]==dep[u]+1) && (w>0)) { int sum=dfs(to,min(delta,w)); if(!sum) { dep[to]=INF; // 如果已经搜到这条边的剩余流量为0，那么就标记这个点不可再走了 } edge[i].v-=sum; edge[i^1].v+=sum; //正向和反向边处理 delta-=sum; //看图 if(!delta) { break; //如果没有剩余流量，就推出 } } } return flow-delta; // } int Read() { int f=1,k=0; char c=getchar(); while(c!='-' && (c<'0' || c>'9')) { c=getchar(); } if(c=='-') { f=-1; c=getchar(); } while(c>='0' && c<='9') { k=(k<<3) + (k<<1) + c - 48; c=getchar(); } return f*k; } int main () { freopen("#2634.in","r",stdin); n=Read(); m=Read(); s=Read(); t=Read(); int u,v,w; for(int i=1;i<=m;i++) { u=Read(); v=Read(); w=Read(); add(u,v,w); add(v,u,0); } long long ans=0; while(bfs()) ans+=dfs(s,INF); printf("%lld\n",ans); return 0; }其实delta就是阴影部分，最后答案就是最上面一层（flow）减去阴影（delta）
