【网络流相关】最大流的Dinic算法实现

Luogu P3376

由于\(EK\)算法求最大流时每一次只求一条增广路，时间复杂度会比较高。尽管实际应用中表现比较优秀，但是有一些题目还是无法通过。

那么我们就会使用\(Dinic\)算法实现多路增广。

算法的基本流程如下：

1. \(BFS\)对图进行分层，求出终点所在的层数
2. \(DFS\)对每一条增广路的信息进行更新

仅仅这样看，虽然一次\(BFS\)能找到多条最短增广路，但是信息的更新仍然是逐条增广路进行更新，效率上并没有太大变化。

所以我们需要下面的两个优化：

• 记录起点到节点\(P\)的流\(flow\)和节点\(P\)到终点的流\(used\)。若\(flow=used\)，则不必再进行之后的\(DFS\)了，可以直接回溯。
• 使用一个\(cur\)数组复制链式前向星的\(head\)数组，在\(DFS\)时，\(cur\)数组记录当前处理的边的编号。下次\(DFS\)到这个节点时，可以直接从\(cur\)数组记录的那条边开始。

第二个优化我们称之为当前弧优化。

原理：每一条已经处理完毕的边，必然不能再容纳下更多的流了。

\(Dinic\)的时间复杂度是\(O(n^2m)\)。对于二分图匹配问题，\(Dinic\)的时间复杂度是\(O(m\sqrt n)\)

结合代码进行理解

#include<cstdio>

#include<queue>

using namespace std;

int n,m,num,cnt,u,v,head[20005],cur[20005],dis[20005],ans;

bool vis[20005];

struct data

{

	int to,next,val;

}e[5000005];

void add(int u,int v,int val)

{

	e[++cnt].to=v;

	e[cnt].next=head[u];

	head[u]=cnt;

	e[cnt].val=val;

}

bool bfs(int s,int t)

{

	queue<int> que;

	que.push(s);

	for (int i=1;i<=n;i++) dis[i]=0,vis[i]=false,cur[i]=head[i];

	vis[s]=true;

	dis[s]=1;

	while (!que.empty())

	{

		int now=que.front();

		que.pop();

		for (int i=head[now];i;i=e[i].next)

		{

			v=e[i].to;

			if (!vis[v]&&e[i].val>0)

			{

				dis[v]=dis[now]+1;

				vis[v]=true;

				if (v==t) return true;

				que.push(v);

			}

		}

	}

	return false;

}

int dfs(int now,int t,int flow)

{

	if (!flow||now==t) return flow;

	int used=0;

	for (int i=cur[now];i;i=e[i].next)

	{

		cur[now]=i;//当前弧优化

		v=e[i].to;

		if (dis[now]+1!=dis[v]) continue;

		int tmp=dfs(v,t,min(flow-used,e[i].val));

		if (tmp)

		{

			e[i].val-=tmp;

			e[i^1].val+=tmp;

			used+=tmp;

			if (flow-used==0) return flow;

		}

	}

	return used;

}

void Dinic(int s,int t)

{

	while (bfs(s,t)) ans+=dfs(s,t,0x7fffffff);

}

int main()

{

	int s,t,w;

	scanf("%d%d%d%d",&n,&m,&s,&t);

	cnt=1;

	for (int i=1;i<=m;i++)

	{

		scanf("%d%d%d",&u,&v,&w);

		add(u,v,w);

		add(v,u,0);

	}

	Dinic(s,t);

	printf("%d",ans);

	return 0;

}