39.网络流入门

1 基本知识

1.1 问题简介

在生活中，许多系统都包含了流量这一概念，例如：自来水系统的水流、财务系统的现金流、互联网中的信息流等等。而他们都包含通道、流量、流速、上限等性质，因此我们通常将关于它们的问题抽象成图论的形式。

网络流就是在图论中用来解决相关问题的一个适用范围相当广的模型，相关的算法也非常多。尽管如此，网络流中的概念、思想和基本算法并不难理解。在本节我们将介绍一些基本的内容和算法，作为网络流问题的引入。

1.2 抽象形式

网络 $G=(V,E)$ 是指一种特殊的有向图，在具备基本的有向图特性之外，其最大不同在于有容量和源汇点。

• $E$ 的每条有向边 $(u,v)\in E$ 都有一个被称为容量的权值 $c(u,v)$。若 $(u,v)\notin E$，假定 $c(u,v)=0$ 可不失一般性；
• $V$ 中有两个特殊的点 $S,T\in V$：源点 $S$ 和汇点 $V$ 且 $S\ne T$；
• 有时候我们还会给定一个单位费用 $w(u,v)$，当边 $(u,v)$ 的流量为 $f(u,v)$ 时，它的花费即为 $f(u,v)w(u,v)$。

对于网络 $G$，我们定义一个流函数 $f(u,v)$，它表示一个从边集 $E$ 到整数集或实数集的函数，它具有以下性质。

• 容量与流量：对于每条边，流经该边的流量不得超过该边的容量，即 $f(u,v)\le c(u,v)$；
• 流量守恒：除源汇点外，任意结点 $x$ 的流入与流出相同，即 $\forall x\ne S,T,{\sum }_{(u,x)\in E}f(u,x)={\sum }_{(x,v)\in E}f(x,v)$。

此外我们定义 $f(u,v)=-f(v,u)$ 来表示一个反向边的负流量，这个定义在具体的算法中有很大的作用。

给定一个网络 $G=(V,E)$，设源点汇点分别为 $S,T$，若一个边集 $E^{\prime }\subseteq E$ 被删去后，$S,T$ 不在连通，则我们称该边集 $E^{\prime }$ 为网络的割。

1.3 常见问题类型

常见的网络流问题包括但不限于以下类型问题。

• 最大流问题：对于网络 $G=(V,E)$，给每条边指定流量，得到合适的流 $f$，使得 $f$ 的流量尽可能大。此时我们称 $f$ 是 $G$ 的最大流。我们还可以用最大流的方式求解二分图匹配问题。
• 最小割问题：对于网络 $G=(V,E)$，找到合适的割 $E^{\prime }$，使得 $E^{\prime }$ 的总容量尽可能小。此时我们称 $E^{\prime }$ 的总容量是 $G$ 的最小割。
• 最小费用最大流问题：对于网络 $G=(V,E)$，对于 $G$ 所有可能的最大流，我们称其中总费用最小的一种为最小费用最大流。

2 最大流问题

2.1 增广路

对于边 $(u,v)$，我们将其容量与流量之差称为剩余容量 $c_f(u,v)$，即 $c_f(u,v)=c(u,v)-f(u,v)$。

我们将 $G(V,E)$ 中所有结点和剩余容量大于 $0$ 的边构成的子图称为残量网络 $G_f(V,E_f)$，其中 E f = { ( u , v ) ∣ c f ( u , v ) > 0 } E_f=\left\{(u,v) \mid c_f(u,v)>0\right\} Ef​={(u,v)∣cf​(u,v)>0}。

我们将 $G_f$上一条从源点 $S$ 到汇点 $T$ 的路径称为增广路。对于一条增广路，我们给每一条边 $(u,v)$ 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广。我们可以知道，当增广路不存在时，当前的流即为最大流。由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。

2.2 Edmonds-Karp 算法

利用增广路寻找最大流的最简单方法就是 Edmonds-Karp 算法，核心思想就是不断使用 BFS 来寻找增广路，直到网络中不存在增广路为止。

特别注意，当 $f(u,v)>0$ 时，我们有 $f(v,u)<0<c(y,x)$。因此我们在 EK 算法中需要考虑到它的反向边，此时反向流量的用意即为减少之前的流量。

void bfs()
{
    queue<ll> q;
    q.push(S);
    memset(pre, -1, sizeof(pre));
    while(!q.empty())
    {
        ll u = q.front();
        q.pop();
        for(ll i = p[u]; i != -1; i = e[i].next)
        {
            ll v = e[i].v, c = e[i].c;
            if(pre[v] == -1 && c > 0)
            {
                pre[v] = i;
                q.push(v);
                if(v == T)
                    return;
            }
        }
    }
}
ll EK()
{
    ll ret = 0;
    while(1)
    {
        bfs();
        if(pre[T] == -1)
            break;
        ll Min = inf;
        for(ll u = T; u != S; u = e[pre[u]].u)
            Min = min(Min, e[pre[u]].c);
        for(ll u = T; u != S; u = e[pre[u]].u)
        {
            e[pre[u]].c -= Min;
            e[pre[u] ^ 1].c += Min;
        }
        ret += Min;
    }
    return ret;
}

EK 算法的时间复杂度较高，可以计算得知为 $O(n{m}^2)$。然而在实际应用中效率往往更高，大概能处理规模为 $10^3\sim 10^4$ 的网络。

2.3 Dinic 算法

从上面 EK 算法的流程中我们不难发现，EK 算法每次都会遍历整个残量网络，但是最终都只会找出一条增广路，这样的效率很低。因此 Dinic 算法就是在寻找增广路的问题上进行了优化。

我们设 $d[x]$ 表示节点的层级，即源点 $S$ 到 $x$ 的最少边数，我们可以根据层级构造分层图。我们在 Dinic 算法中，只会考虑低层级结点流向高层级结点的情况，因此减少了回流情况。而在 Dinic 算法中，我们一次可以找到多条增广路，因此大大提高了效率。

Dinic 算法重复以下步骤，直到残量网络中 $S$ 和 $T$ 不连通：

• 在残量网络中按 BFS 求出结点层级，构造分层图；
• 在分层图上 DFS 寻找增广路，在回溯时实时更新残量网络。因为每个点可以延伸出多条出边，因此一次 DFS 即可找到多条增广路，提高了算法效率。

bool bfs()
{
	memset(d, -1, sizeof(d));
	d[S] = 1;
	queue<ll> q;
	q.push(S);
	while(!q.empty())
	{
		ll u = q.front();
		q.pop();
		for(ll i = p[u]; i != -1; i = e[i].next)
		{
			ll v = e[i].v, c = e[i].c;
			if(d[v] == -1 && c > 0)
			{
				d[v] = d[u] + 1;
				q.push(v);
				if(v == T)
					return true;
			}
		}
	}
	return false;
}
ll dfs(ll u, ll flow)
{
	if(u == T)
		return flow;
	ll res = 0;
	for(ll i = p[u]; i != -1; i = e[i].next)
	{
		ll v = e[i].v;
		if(d[u] + 1 == d[v] && e[i].c > 0)
		{
			ll tmp = dfs(v, min(flow, e[i].c));
			if(!tmp)
				d[v] = 0;
			flow -= tmp;
			e[i].c -= tmp;
			e[i ^ 1].c += tmp;
			res += tmp;
			if(flow == 0)
				break;
		}
	}
	return res;
}
void Dinic()
{
	ll ans = 0;
	while(bfs())
		ans += dfs(S, inf);
	printf("%lld\n", ans);
}

最终算法的时间复杂度为 $O(n^{2}m)$。然而在实际应用中效率往往更高，大概能处理规模为 $10^4\sim 10^5$ 的网络。而 Dinic 算法求解二分图匹配问题的时间复杂度为 $O(m\sqrt{n})$。

5 作业

P3376 【模板】网络最大流