网络流最大流 Dinic算法

本文主要是介绍网络流最大流 Dinic算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

O（N^2*M）的算法
比EK的O（N*M^2）优很多
EK通常解决10^3 –10^4规模的网络
而dinic能解决10^4–10^5的网络

Dinic算法的思想也是分阶段地在层次网络中增广。它与最短增广路算法不同之处是：最短增广路每个阶段执行完一次BFS增广后，要重新启动BFS从源点Vs开始寻找另一条增广路;而在Dinic算法中，只需一次DFS过程就可以实现多次增广，这是Dinic算法的巧妙之处。Dinic算法具体步骤如下:

（1）初始化容量网络和网络流。

（2）构造残留网络和层次网络，若汇点不再层次网络中，则算法结束。

（3）在层次网络中用一次DFS过程进行增广，DFS执行完毕，该阶段的增广也执行完毕。

（4）转步骤（2）。

贴模板：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring> 
#include<cmath>
#define N 10005
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t,cnt=1,head[N],incf[N],d[N],maxflow; struct Node{int to,nxt,val;
}edge[M];void add(int x,int y,int z)
{cnt++;edge[cnt].to=y;edge[cnt].nxt=head[x];edge[cnt].val=z;head[x]=cnt;
}bool bfs()
{memset(d,0,sizeof d);queue<int> q;q.push(s);  d[s]=1;while(q.size()){int u=q.front(); q.pop();for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(edge[i].val && !d[v]){q.push(v);d[v]=d[u]+1;if(v==t) return true;}}}return false;
}int dinic(int x,int flow)
{if(x==t) return flow;int res=flow,k;for(int i=head[x];i && res;i=edge[i].nxt){int v=edge[i].to;if(edge[i].val && d[v]==d[x]+1){k=dinic(v,min(res,edge[i].val));if(!k) d[v]=0;  //剪枝，去掉增广完毕的点edge[i].val-=k;edge[i^1].val+=k;res-=k;}}return flow-res;
}int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z); add(y,x,0);//成对储存 }int flow=0;while(bfs()){while(flow=dinic(s,inf)) maxflow+=flow;}printf("%d",maxflow);return 0;
}