网络流入门——dinic算法

程序员文章站 2024-03-04 15:19:29

...

废话

一个炒鸡有用的工具，省选必备。

正题

先把例题摆出来： $click~here$ 。

题目大意： 有一张有向图，每条边有一个流量上限，问最多能从点 $1$ 往点 $n$ 流多少流量。

网络流算法，讲真，相当暴力，不作任何优化的话，做法大概就是：从点 $1$ 往外 $dfs$ ，找到一条能往 $n$ 流流量的路时，就暴力流过去，能流多少流多少，而经过的边的流量上限自然相应减少。

找到的这条路，在网络流中，我们称之为增广路，而能流过去的最大流量，称为最大流。

显然上面的爆搜很可能会做出不优秀的决策，最经典的就是这张图了：
网络流入门——dinic算法
噢，顺便说一下，图这种东西，在网络流里面，我们称之为网络qwq。

显然，当增广路为 $1\to 2\to 4$ 和 $1\to 3\to 4$ 时，能得到最大流 $2$ ，但是如果爆搜搜到了 $1\to 2\to 3\to 4$ 这样的憨憨增广路，那么流量只有 $1$ 了。

为了避免这种情况，我们需要引入一个优化：反向弧，也就是对于每条边，建一条反向边，一开始的流量为 $0$ ，当正向边流量减少时，反向边流量相应增加，反向边流量减少时，正向边亦然。

这有什么用呢？来看看有了反向边后，假如找到了 $1\to 2\to 3\to 4$ 这样的增广路会怎么样：
网络流入门——dinic算法
又要来补充一些概念了……这种被跑过的图，我们称之为残余网络。

此时流量变成了这样，然后发现，我们又可以找到一条增广路： $1\to 3\to 2 \to 4$ 。

没错， $2\to 3$ 的反向边发挥了作用，先走了 $2\to 3$ ，再走了它的反向边，那么这条边相当于没走，所以上面走的两条增广路其实就相当于 $1\to 2\to 4$ 和 $1\to 3\to 4$ 这两条。

反向边的作用浮出水面：提供反悔的机会。

要说具体一点的话，就是假如有这样一条不优秀的 $S\to ...\to a\to b \to d\to ...\to T$ ，优秀的走法应该是： $S\to ...\to a\to$ $c$ $\to ...\to T$ ，那么反向边就会提供一条这样的路径： $S\to ...\to b\to a\to c\to ...\to T$ ， $a\to b$ 这条边的正向边和反向边都被走了一次，相当于没走，所以事实上我们得到的两条增广路为 $S\to ...\to a\to c\to ...\to T$ 和 $S\to ...\to b\to d\to ...\to T$ 。

（不明白可以画个图手玩一下qwq）

但是这样的时间复杂度依然不能让人满意，所以还有几个优化：

发现如果要求最大流的话，就要让增广路经过的边数尽可能少，这样每次影响的边数也尽可能少，能找到的增广路就会尽可能多，可以减少反向边的使用次数，尽可能每次都能找到优秀的增广路。
要做到这一点的话，就在每次求增广路前预处理一个 $h$ 数组， $h[i]$ 表示从源点到点 $i$ 至少经过多少个点（边也行，差不多），然后在求增广路时，只有满足了 $h[y]=h[x]+1$ 时， $x$ 才往 $y$ 那里搜。
每次找到一条增广路就重新来这样的做法太慢了，我们可以去找尽可能多的增广路，直到找不到位为止，然后重新求一次 $h$ 数组再来。
当前弧优化（建议结合代码理解）：比如说，上一次搜索到点 $x$ 时，枚举到第 $k$ 个儿子就没有流量了，此时我们选择退出循环，那么下一次来点 $x$ 时，直接从第 $k$ 个儿子开始往下枚举即可，不需要再从第一个儿子开始了。

有了这些优化后，你就得到了一个优秀的网络流算法： $dinic$ 算法。

还有另外一个网络流算法，叫 $SAP(ISAP)$ ，有兴趣可以去搜搜，大致思路是：假如出现了某个 $k$ ，满足所有 $h[i]=k$ 的点都不能再往下增广了（即出现断层），那么就直接原地求新的 $h$ ，然后继续搞。

$dinic$ 代码如下（上面模板题的 $AC$ 代码）：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 210

int n,m;
struct edge{int y,z,next;};
edge e[maxn<<1];
int first[maxn],cur[maxn],len=1;//注意len是1，这样方便找反向边
void buildroad(int x,int y,int z)
{
	e[++len]=(edge){y,z,first[x]};
	first[x]=len;
}
int h[maxn],q[maxn],st,ed;
bool bfs()//求h数组
{
	memset(h,0,sizeof(h));
	for(int i=1;i<=n;i++)cur[i]=first[i];//cur记录当前弧，一开始初始化为first
	st=ed=1;q[st]=1;h[1]=1;
	while(st<=ed)
	{
		int x=q[st++];
		for(int i=first[x];i;i=e[i].next)
		//假如e[i].y是第一次来，并且这条边还有流量，才去更新他，没有流量的边不考虑
		if(h[e[i].y]==0&&e[i].z>0)h[q[++ed]=e[i].y]=h[x]+1;//将其加入队列并更新
	}
	return h[n]>0;
	//h[n]=0表示不存在能到达n的增广路，那么就返回false，告诉主程序没必要继续dfs了
}
int dfs(int x,int flow)//flow表示此时x拥有的流量，dfs的返回值表示有多少流量流到了汇点
{
	if(x==n)return flow;//假如流到了汇点，那么汇点照单全收
	int tt=0;//记录流到汇点的流量
	for(int i=cur[x];i;i=e[i].next)//从当前弧开始
	{
		int y=e[i].y;cur[x]=i;//别忘了更新
		if(h[y]==h[x]+1&&e[i].z)
		//第一个条件正如上面所说，然还后要求这条边有流量（不然怎么把流量流给y）
		{
			int p=dfs(y,min(flow-tt,e[i].z)); tt+=p;
			e[i].z-=p;e[i^1].z+=p;//正向边减去，反向边加上，注意，正向边和反向边是相对的
			if(tt==flow)break;//没流量了就不用循环了
		}
	}
	if(!tt)h[x]=0;//假如这次一滴流量都没流过去，那么以后就没必要来x了
	return tt;
}

int main()
{
	scanf("%d %d",&m,&n);
	for(int i=1,x,y,z;i<=m;i++)
	scanf("%d %d %d",&x,&y,&z),
	buildroad(x,y,z),buildroad(y,x,0);//别忘了建反向边
	int ans=0;while(bfs())ans+=dfs(1,2147483640);//源点流量无限
	printf("%d",ans);
}

最坏时间复杂度为 $O(n^2m)$ ，但是要记住，网络流的时间复杂度一般跑不满。

简单应用

first

二分图最大匹配问题。

虽然可以用匈牙利算法，但是网络流也很优秀。

题目大意： 有一堆男生和一堆女生，给出若干个关系，每个关系表示为 $x,y$ ，表示第 $x$ 个男生和第 $y$ 个女生想成为 $cp$ （当然一个男生可以和多个女生有关系，一个女生也可以和多个男生有关系），然后请你成全尽可能多的人，输出最大 $cp$ 数。（显然，一个人不能和多个人组成 $cp$ ）。

网络流的题做起来一般分为两步：建模型，套板子。几乎所有题目的难点都是第一步。

这题的模型（也就是图）算是好建的，创造一个超级源点（没什么特别意思，就是源点，但是以后你会看到很多这样的说法）和一个超级汇点，源点向所有男生连边，所有女生向汇点连边，然后每对关系中男生向女生连边，所有边的流量都是 $1$ ，最后跑一发最大流就是答案。

简单分析一下这些边的意义：源点向男生连流量为 $1$ 的边，代表每个男生最多得到 $1$ 的流量，那么这限制了每个男生只能找 $1$ 个女生，而女生向汇点连流量为 $1$ 的边，代表每个女生只能被 $1$ 个男生选择，正好对应了上面的要求。而中间根据关系连的边，流量其实无所谓qwq。

second

这题是想给大家讲一个网络流经典的建图套路。

题目是这样的：给出一张有向图，找出尽可能多的从起点到终点的路径，这些路径不能经过相同的点（即每个点只能存在于至多 $1$ 条路径）。

这个直接建图跑肯定有问题，不能满足每个点只能用一次这个限制，这种限制，我们一般用拆点解决，即每个点拆成两个点 $A$ 和 $A'$ ，连进来的边连着 $A$ ，连出去的边连着 $A'$ ，然后 $A$ 和 $A'$ 之间连一条边，流量为这个点最多能用多少次，本题中就是 $1$ 了。

last

想要更多应用的话就去刷网络流 $24$ 题吧！

网络流入门——dinic算法

废话

正题

简单应用

first

second

last