dinic模板

dinic模板

Dinic算法的大致步骤

1、建立网络（包括正向弧和反向弧（初始边权为0）），将总流量置为0

2、构造层次网络（怎么又有新概念 T_T）

简单的说，就是求出每个点u的层次，u的层次是从源点到该点的最短路径（注意：这个最短路是指弧的权都为1的情况下的最短路），若与源点不连通，层次置为-1

一遍BFS轻松解决

3、判断汇点的层次是否为-1

是：再见，算法结束，输出当前的总流量

否：下一步

4、用一次DFS完成所有增广，增广是什么呢？

增广（我的理解）：通过DFS找上述的增广路，找到了之后，将每条边的权都减去该增广路中拥有最小流量的边的流量，将每条边的反向边的权增加这个值，同时将总流量加上这个值

DFS直到找不到一条可行的从原点到汇点的路

5、goto 步骤2

细节处理，如何快速找到一条边的反向边：边的编号从0开始，反向边加在正向边之后，反向边即为该点的编号异或1

复杂度：理论上来说，最慢应该是O((n^2)*m)，n表点数，m表边数，实际上呢，应该快得不少

代码实例：（参见洛谷P3376）

传送门[>洛谷<] 重要提示：您的等级必须达到蓝色以上，否则后果自负

弧优化

在DFS的时候记录当前已经计算到第几条边了，避免重复计算。

然后在下一次构建层次网络的注意将head数组还原

By LinZhengmin’s算法 网络最大流Dinic

这是以前打的标程，备个份

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct qy
{
	int x,y,flow;
};

int n,m,i,j,k,S,T,x,y,z,ans;
qy l[200005];
int next[200005],last[100005],tot,cur[100005];
int depth[100005],list[100005],head,tail;

void insert(int x,int y,int z)
{
	tot++;
	l[tot].x=x;l[tot].y=y;l[tot].flow=z;
	next[tot]=last[x];
	last[x]=tot;
}

int bfs()
{
	memset(depth,0,sizeof(depth));
	depth[S]=1;
	list[1]=S;head=0;tail=1;
	while (head<tail)
	{
		int x=list[++head];
		for (int i=last[x];i>=1;i=next[i])
		{
			int y=l[i].y;
			if ((depth[y]==0)&&(l[i].flow>0))
			{
				depth[y]=depth[x]+1;
				list[++tail]=y;
				if (y==T) return 1;
			}
		}
	}
	return 0;
}

int dfs(int x,int have)
{
	int flow=0,tt;
	if (x==T) return have;
	for (int i=cur[x];i>=1;cur[x]=i=next[i])
	{
		if (flow==have) return flow;
		int y=l[i].y;
		if (depth[y]==depth[x]+1)
		{
			tt=dfs(y,min(have-flow,l[i].flow));
			flow+=tt;
			l[i].flow-=tt;
			l[i^1].flow+=tt;
		}
	}
	return flow;
}

void dinic()
{
	int s;
	while (bfs())
	{
		for (i=1;i<=n;i++)
		cur[i]=last[i];
		while (s=dfs(S,10000000))
			ans+=s;
	}
}

int main()
{
	freopen("read.in","r",stdin);
	scanf("%d%d",&m,&n);
	S=1;T=n;
	tot=1;
	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);
		insert(y,x,0);
	}
	dinic();
	printf("%d",ans);
}