最大流与最小割

前言

笔者为网络流初学者，可能文章有诸多不足，请指出。

亮点在于 vector 存图、反边作用的解释、代码的注释。

初学者可暂时跳过下面这段“关于 vector 存图”，学完算法在回来看。

关于 vector 存图

很多网上的资料（视频、题解）的最大流算法为了方便找反边，都使用了链式前向星。

但是！

vector 党表示不服！

于是在进行学习后，笔者归纳出了两种 vector 存图并快速找反边的方法。

代码。

存储反边编号

一般 vector 实现邻接表是形如这样的：（在最大流相关算法中）

struct edge
{
	int v,w;
};
vector<edge> e[N];
inline void addedge(int u,int v,int w)
{
	e[u].push_back({v,w});
	e[v].push_back({u,0});
}

但是这种存储方法无法快速找到反边。
考虑在结构体 edge 中添加一个信息 x：

struct edge
{
	int v,w,x;
};

表示反边为 e[v][x]。那么加边时也相应的需要修改：

inline void addedge(int u,int v,int w)
{
	e[u].push_back({v,w,int(e[v].size())});
	e[v].push_back({u,0,int(e[u].size()-1)});
}

这样就可以快速实现找反边操作了。（关于为什么是 int(e[v].size())、int(e[u].size()-1) 请自行思考。）

注意，EK 算法中 int pre[N] 数组则需要改成 pair<int,int> pre[N]，分别表示来自 first 号点和它的 second 号边。

将边存入池子并保存编号

我们可以使用两个 vector 实现更方便的存边方式：

vector<edge> es;
vector<int> e[N];

其中 es 存了所有边，e[u] 中存 u 的所有出边在 es 中的编号。

于是，如果我们需要知道边 e[u][i] 的信息，只需要访问 es[e[u][i]]。

而 e[u][i] 的反边即为 e[u][i]^1，与传统链式前向星的访问反边方式类似。

存边时：

e[u].push_back(es.size());
es.push_back({v,ll(w)});
e[v].push_back(es.size());
es.push_back({u,0ll});

---

正文开始。

网络流基础知识

以下记 $|V|=n,|E|=m$。

网络（network，$G$），即一种特殊的带权有向图 $G=(V,E)$，特别的是，其有特殊的源（source）$s$、汇（target）$t$ 二点。一般认为 $s,t$ 是固定的两点。

流（flow，$f$），为 $E\to\Bbb{R}$ 的函数，其满足 $\forall u\ne s\land u\ne t,\sum_{w}f(w,u)=\sum_{v}f(u,v)$，即除 $s,t$ 外的点满足进入 $u$ 的流等于出 $u$ 的流。如果 $(u,v)\notin E$ 即边 $(u,v)$ 不存在，我们默认 $f(u,v)=0$。（如果一定要较真的话你也可以定义其为 $V\times V\to\Bbb{R}$ 的函数，然后分类讨论。）

净流量（$f$），这里使用了与流同样的记号，为 $V\to\Bbb{R}$ 的函数，定义为 $f(u)=\sum_{v}f(u,v)-\sum_{w}f(w,u)$。容易发现，由于流的性质，除 $s,t$ 外的点的净流量均为 $0$。由于 $s$ 流出的量最终必须流向 $t$，故有 $f(s)=-f(t)$

一个流的流量（value，$|f|$），定义为 $s$ 的净流量，即 $|f|=f(s)=-f(t)$。

容量（capacity，$c$），即普通带权有向图的边权，为 $E\to\Bbb{R}_{\ge 0}$ 的函数，一般由题目给出。我们说一个流是合法的当前仅当 $\forall e\in E,0\le f(e)\le c(e)$。若 $e\in E$ 满足 $f(e)=c(e)$，我们说它是满流的。同样的，若 $e\in E$ 满足 $f(e)=0$，我们说它是空流的。如果 $(u,v)\notin E$ 即边 $(u,v)$ 不存在，我们定义 $c(u,v)=0$。

最大流问题（maximum flow problem），即对于任意合法的流 $f$，求出 $\max|f|$，此时 $f$ 称为 $G$ 的最大流。

割（cut，$(S,T)$），是一种点集 $V$ 的划分，即 $S\cup T=V,S\cap T=\varnothing$ 且满足 $s\in S,t\in T$。

一个割的容量（capacity，$||S,T||$），定义为

$||S,T||=\sum_{\mathclap{u\in S,v\in T}}c(u,v)$

即从 $S\to T$ 的连边的容量的和。注意没有 $T\to S$ 的连边！这里我们再次用了“容量（capacity）”这个词，故需区分其与边的容量。

最小割问题（minimum cut problem），即对于任意割 $(S,T)$，求出 $\min||S,T||$，此时 $(S,T)$ 称为 $G$ 的最小割。

---

以上是冷冰冰的定义，可以直接生硬地理解，也可以用现实中的例子如水流来理解。看上去很长，但这里需要强调定义的重要性。笔者发现，网上资料的许多定义是不正确的。结合证明时，读者往往会不知所措。

如有资料称 $f$ 为 $E\to\Bbb{R}$ 的函数，却又说“对于每条边 $(u,v)$，我们都新建一条反向边 $(v,u)$。我们约定 $f(u,v)=-f(v,u)$”。明明 $(v,u)\notin E$，却将 $(v,u)$ 代入了 $f$。那么 $(v,u)$ 到底在不在 $E$ 中？甚至说 “$f(v,u)$ 的绝对值是无关紧要的”，简直胡扯！这样搪塞其词，只会使读者感到困惑。

很多资料并没有考虑 $(u,v)$、$(v,u)$ 均存在于 $G$ 中的情况（即 $(u,v)\in E\land (v,u)\in E$）。这种情况下，再按照上面的“约定”，$f(v,u)$ 的值到底应该是多少？本文中，我们假定没有这种情况，如果有，这种情况也很好处理——建立中继点即可。事实上，代码实现中我们甚至不需要管这种情况，因为对于每条 $G$ 上的边，我们都有其专属的反向边。换句话说，实现时可能有两条 $(v,u)$，就不存在形式化表达中“到底是那条 $(v,u)$”的问题。

Ford–Fulkerson 增广

Ford–Fulkerson 增广是一种计算最大流的策略。该方法运用了带反悔的贪心，通过寻找增广路来更新并求解最大流。对于此策略的正确性，将在下一节“最大流最小割定理”中讲解。

定义

剩余容量（residual capacity，$c_f(u,v)$），为一个 $V\times V\to\Bbb{R}$ 的函数，定义为

$c_f(u,v)= \begin{cases} c(u,v)-f(u,v)&\text{if $(u,v)\in E$}\\ f(v,u)&\text{if $(v,u)\in E$}\\ 0&\text{otherwise} \end{cases}$

残量网络（residual graph，$G_f$），定义为 $G_f=(V,E_f),E_f=\{(u,v)|c_f(u,v)>0\}$。即原网络中的点和剩余容量 $>0$ 的边构成的图。由于反向边的存在，故不满足 $E_f\subseteq E$。

增广路（augmenting path，$P$），为 $G_f$ 上一条 $s\to t$ 的路径，由于该路径上所有边 $(u,v)$ 的剩余容量 $c_f(u,v)>0$，所以这些边都可以增加流量（或退去反向边的流量），即可以进行增广：设 $\Delta=\min_{(u,v)\in P}c_f(u,v)$，增广后的流为 $f'$，有

$f'(u,v)= \begin{cases} f(u,v)+\Delta&\text{if $(u,v)\in P$}\\ f(u,v)-\Delta&\text{if $(v,u)\in P$}\\ 0&\text{otherwise} \end{cases}$

可以证明增广后 $f'$ 也是合法的。同时 $|f'|=|f|+F>|f|$，故 $f'$ 更优。可以得到，如果在 $G_f$ 上存在 $s\to t$ 的路径，那么 $f$ 不是最大流。

为什么要使 $E_f$ 中存在反向边？

注意到 Ford–Fulkerson 增广属于贪心，但反向边支持反悔（如果增广 $(v,u)$，即减少了 $f(u,v)$，于是可以做到反悔）。

可以通过以下例子理解：

其中 $s=1,t=6$，所有边的容量均为 $1$。

假如第一次 bfs 选择了增广路 $1\to 2\to 4\to 6$，那么如果没有反边，残量网络中 $s,t$ 就不连通了，算法结束，求出的最大流量为 $1$。

但显然如果增广 $1\to 2\to 5\to 6,1\to 3\to 4\to 6$ 这两条路，那么最大流量为 $2$，优于 $1$。

如果将反边进行操作，增广完 $1\to 2\to 4\to 6$，$c_f(2,4)=1-1=0,c_f(4,2)=1$，也就是说，边 $(2,4)$ 虽然不再在残量网络中，但 $(4,2)$ 被添加进了残量网络。下一次 bfs 时，就可以通过 $1\to 3\to 4\to 2\to 5\to 6$ 进行增广了。这样，$(2,4),(4,2)$ 的加流相互抵消，等价于增广 $1\to 2\to 5\to 6,1\to 3\to 4\to 6$。

这时可能你心里会想：增广（A）$1\to 2\to 4\to 6,1\to 3\to 4\to 2\to 5\to 6$ 为什么一定等价于增广（B）$1\to 2\to 5\to 6,1\to 3\to 4\to 6$？如果边权不一样怎么办？比如如果其他所有边的容量都是 $114514$，而 $c_f(2,4)=1$，A 的最大流只有 $1+1=2$，而 B 有 $114514+114514=229028$ 呢！实际上对于这个情况，A 增广后并没有结束，因为 $s,t$ 还连通着。算法会接着增广 B，以达到最大流。

这样就实现了反悔。于是，我们可以一直增广，直到 $G_f$ 中 $s,t$ 不再连通，即没有增广路可以增加流量了，此时 $f$ 即为该网络的最大流，它是由众多增广出的流叠加而成。

比较抽象，接下来看看算法实现。

EK 算法

EK 算法的本质就是通过在残量网络 $G_f$ 上 bfs 找增广路，进行增广。

算法流程

• 初始化。

  注意，反向边也要存，存图时虽存的是原网络，但边权表示的是 $c_f$ 而非 $c$ 或 $f$。

• bfs 在 $G_f$ 上找增广路。如果 $G_f$ 上存在 $s\to t$ 的路径，则找到了新的增广路。

• 增广。

• 重复 bfs、增广，直到 $G_f$ 中 $s,t$ 不再连通，即不存在增广路，此时 EK 算法结束。

可以发现，由于使用的是 bfs，每次增广的增广路都是最短的。

为什么说存的是原网络而非残量网络？

如果要存残量网络，每次增广后需要将 $c_f(u,v)=0$ 的边 $(u,v)$ 删掉，太过麻烦。而直接存原网络，bfs 时直接判断 $c_f(u,v)$ 是否 $>0$，就知道该边是否在 $G_f$ 中，所以边权维护 $c_f$。

还是不懂可以看代码理解。

代码

题目：P3376 【模板】网络最大流

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
constexpr int N=214;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct edge
{
	int v;// 边 (u,v)
	ll c;// 准确来说，c_f
};
vector<edge> es;// 边集
vector<int> e[N];// 存出边

int n,m,s,t;

namespace EK
{
	bitset<N> vis;
	int pre[N];// 存增广路上的前驱
	ll flow[N];// flow[u]：能流到 u 的最大流量
	bool bfs()
	{
		queue<int> q;
		vis.reset();
		vis[s]=true;
		q.push(s);
		flow[s]=INF;// 从源点流出的“水量”应是无穷大的，但由于水管不够大，被阻塞
		int u,l,v;
		ll c;
		while(!q.empty())// bfs
		{
			u=q.front();
			q.pop();
			l=e[u].size();
			for(int i=0;i<l;i++)// 遍历出边
			{
				v=es[e[u][i]].v;
				c=es[e[u][i]].c;
				if(!vis[v]&&c>0)// 未遍历过且存在于残量网络中
				{
					vis[v]=true;// 标记
					flow[v]=min(flow[u],c);// 取 min
					pre[v]=e[u][i];// 标记前驱
					if(v==t)return true;// 如果搜到 t，则找到增广路，返回
					q.push(v);
				}
			}
		}
		return false;// 无增广路
	}
	ll EK()
	{
		ll r=0ll;// 初始流量
		while(bfs())// 找增广路
		{// 如果有增广路
			r+=flow[t];// 增加网络流量
			for(int i=t;i!=s;i=es[pre[i]^1].v)// 增广路上的每条边
			{ // 更新 c_f
				es[pre[i]].c-=flow[t];// 正边
				es[pre[i]^1].c+=flow[t];// 反边
			}
		}
		return r;// 无增广路，算法结束
	}
}//^ namespace EK

int main()
{
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=1,u,v,w;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		e[u].push_back(es.size());// 采用类似链式前向星的存边法
		es.push_back({v,ll(w)});
		e[v].push_back(es.size());
		es.push_back({u,0ll});
	}
	printf("%lld",EK::EK());
	return 0;
}

时间复杂度

单轮 bfs 增广的时间复杂度是 $O(m)$。

增广总轮数的上界是 $O(nm)$。但笔者不会证，干脆不要乱证。OIer 不需要证明。

于是最终时间复杂度为 $O(nm^2)$。为 $O(n^5)$ 量级。实际上跑不满，但容易被卡。

Dinic 算法

由于 EK 经常被卡，引出 Dinic 算法。

如何优化 EK

考虑 EK 到底慢在哪。

EK 本质上是一次一次的 bfs 增广，每次只能增广一条最短的增广路。Dinic 使用分层图后，不仅满足增广最短增广路，同时可一次性增广多条增广路。

定义

设 $u$ 到 $s$ 的距离为 $d(u)$，它可以用 bfs 求得。注意这里距离的定义为从 $s$ 到 $u$ 所需要经过的最少边数。

层次图（Level Graph，$G_L$），是在 $G_f=(V,E_f)$ 的基础上，设 $E_L=\{(u,v)|(u,v)\in E_f,d(u)+1=d(v)\}$，那么 $G_L=(V,E_L)$。也就是说，我们从 $E_f$ 中删除了一些边，使经过 $u$ 的流量只能流向下一层的结点 $v$。

阻塞流（Blocking Flow，$f_b$），是在当前 $G_L$ 上找到的一个极大的流 $f_b$。

算法流程

• 在 $G_f$ 上 bfs 出层次图 $G_L$。
• 在 $G_L$ 上 dfs 出阻塞流 $f_b$。
• 将 $f_b$ 并到原先的流 $f$ 中，即 $f\gets f+f_b$。
• 重复以上过程直到不存在从 $s$ 到 $t$ 的路径。

具体如何实现 dfs？

我们可以每次 dfs，一找到一条阻塞流的增广流，就立马回溯，进行增广。同时多次 dfs。

但不必如此。常数优化：只需一次 dfs，找到多个增广路一次性增广阻塞流——多路增广优化。

给出 dfs 实现流程：

• 从源点开始 dfs，保存当前点编号 $u$、当前流到 $u$ 的流大小 $flow$。
• 如果 $u=t$，即这股阻塞流已经到达了汇点 $t$，返回 $flow$。
• 对于每条出边指向的点 $v$，如果在层次图上存在边 $(u,v)$，dfs 出 $v$ 的阻塞流 $now$。
• 如果 $now=0$，说明 $v$ 无法增广，将 $d(v)\gets 0$，弃置——无用点优化。
• 现场增广，更新当前点 $u$ 的最大流 $res\gets res+now,flow\gets flow-now$，更新 $c_f(u,v)\gets c_f(u,v)-now,c_f(v,u)\gets c_f(v,u)+now$。
• 返回 $res$。

由于不是 DAG，dfs 可能多次遍历某个点 $u$，每次由入边流入流量时 $u$ 都需要遍历每个出边进行流量的传递，这一过程可能达到 $O(m^2)$。

所以，如果某条出边已无法接受更多流量（$(u,v)$ 无剩余容量或 $v$ 的后侧已阻塞），那么我们下一次遍历 $u$ 时就可以跳过 $(u,v)$。

于是对于每个点 $u$，维护其出边中第一条可尝试的出边。这条边叫当前弧，该做法叫当前弧优化。（其实和欧拉回路很像。）

以上可能讲得不清楚，可参考代码。

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
constexpr int N=214;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct edge
{
	int v;
	ll c;
};

vector<edge> es;// 存图方式同 EK
vector<int> e[N];

int n,m,s,t;

namespace Dinic
{
	int dis[N],fir[N];// dis[u]：s->u 最短距离，fir[u]：u 的出边中第一个有意义的点，即当前弧
	bool bfs()
	{
		fill(fir,fir+N,0);// 清空
		fill(dis,dis+N,0);
		dis[s]=1;
		queue<int> q;
		q.push(s);
		int u,l,v;
		while(!q.empty())// bfs
		{
			u=q.front();
			q.pop();
			l=e[u].size();
			for(int i=0;i<l;i++)
			{
				v=es[e[u][i]].v;
				if(!dis[v]&&es[e[u][i]].c>0ll)// 若未遍历过且有剩余容量
				{
					dis[v]=dis[u]+1;// 标记
					q.push(v);
					if(v==t)return true;// 若找到 t，返回
				}
			}
		}
		return false;// 若无阻塞流，返回
	}
	ll dfs(int u=s,ll flow=INF)// flow：可以流进当前点的流量
	{// 注意，这里的 dfs 不像其他 dfs，可能重复访问一个点
		if(u==t)return flow;// 找到 t，返回流到 t 的流量
		int l=e[u].size(),v;
		ll res=0ll,now,c;
		for(int i=fir[u];i<l;i++)// 从第一个有必要尝试的点开始
		{
			fir[u]=i;// 当前弧优化：维护当前弧指针，注意它只对本轮 dfs 有效，bfs 会清除 fir 数组
			v=es[e[u][i]].v;
			c=es[e[u][i]].c;
			if(dis[v]==dis[u]+1&&c>0ll)// 如果在 G_L 上且有剩余容量
			{
				now=dfs(v,min(flow,c));// dfs 出 v 能流到 t 的阻塞流
				if(now==0ll)dis[v]=0;// 无用点优化：如果已经不能增广 v，则丢弃 v，这样下一次访问 u 并遍历出边时就会忽略 v
				es[e[u][i]].c-=now;// 现场增流
				es[e[u][i]^1].c+=now;
				res+=now;// 更新当前点能流出的最大阻塞流
				flow-=now;// 任务减轻
				if(flow==0ll)return res;// 当前弧优化：如果任务完成，直接 return，非常重要！！！
				// 如果没有上面这一句，Dinic 的复杂度将无法保证，甚至在洛谷模板题上比 EK 跑得还慢！！！
				// 因为不 return 会继续遍历所有出边，但参数 flow=0，没有任何用处，浪费时间。
			}
		}
		return res;
	}
	ll Dinic()
	{
		ll r=0ll;
		while(bfs())r+=dfs();
		return r;
	}
}//^ namespace Dinic

int main()
{
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=1,u,v,w;i<=m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		e[u].push_back(es.size());
		es.push_back({v,ll(w)});
		e[v].push_back(es.size());
		es.push_back({u,0ll});
	}
	printf("%lld",Dinic::Dinic());
	return 0;
}

时间复杂度

单轮 dfs 增广的时间复杂度是 $O(nm)$，增广总轮数的上界是 $O(n)$，于是最终时间复杂度为 $O(n^2m)$。

为 $O(n^4)$ 量级。实际上也跑不满，但据说不卡 Dinic 是所有出题人的共识（惯例）。

称边权为 $0,1$ 的图为单位容量的。

• 在单位容量的网络中，Dinic 算法的单轮增广的时间复杂度为 $O(m)$。
• 在单位容量的网络中，Dinic 算法的增广轮数是 $O(\sqrt{m})$ 的。
• 在单位容量的网络中，Dinic 算法的增广轮数是 $O(n^{2/3})$ 的。

于是单位容量的网中网络流的复杂度为：$O(m\min(\sqrt{m}, n^{2/3}))$，二分图匹配就可以做到这个复杂度。

正确性

每次建立层次图后都可以进行多次增广，无法增广时重新建立层次图，此时的层次图不再包含之前进行增广后满载的边。无法建立层次图时，说明源点到汇点的任意一条简单路径中，都至少有一条边满载，这也在直观上验证了最小割最大流定理。

最大流最小割定理

对于网络 $G=(V,E)$，源点 $s$，汇点 $t$，有以下三个条件互相等价：

1. $f$ 为最大流
2. 残量网络 $G_f$ 上不存在增广路
3. 存在割 $(S,T)$ 使得 $||S,T||=|f|$

引理

先从一个引理开始：$|f|\le||S,T||$。

也就是说任意一个流的流量都不会大于任意一个割的容量。进一步地，就是最大流流量不大于最小割容量。

设 $u\in S,v\in T$。因为流从 $S$ 中的点流到 $T$ 中，必须跨过一条 $(u,v)$ 边。即使 $(u,v)$ 均满流，即 $f(u,v)=c(u,v)$，也只有 $|f|=||S,T||$。此时所有从 $S$ 到 $T$ 的边都已满流，无法再增加流量，所以有 $|f|\le||S,T||$。

形式化的证明：

$\footnotesize \begin{aligned} |f|&=f(s)&\text{基本性质}\\ &=\sum_{u\in S}f(u)&\text{所有 $u\in S,u\ne s$ 均满足 $f(u)$=0}\\ &=\sum_{u\in S}\left(\sum_{v\in V}f(u,v)-\sum_{v\in V}f(v,u)\right)&\text{净流量 $f(u)$ 的定义：出量$-$入量}\\ &=\sum_{u\in S}\left(\sum_{v\in T}f(u,v)+\sum_{v\in S}f(u,v)-\sum_{v\in T}f(v,u)-\sum_{v\in S}f(v,u)\right)&\text{将 $v\in V$ 分类讨论：$v\in S,v\in T$}\\ &=\sum_{u\in S}\left(\sum_{v\in T}f(u,v)-\sum_{v\in T}f(v,u)\right)+\sum_{u\in S}\sum_{v\in S}f(u,v)-\sum_{u\in S}\sum_{v\in S}f(v,u)&\text{分离}\\ &=\sum_{u\in S}\left(\sum_{v\in T}f(u,v)-\sum_{v\in T}f(v,u)\right)&\text{抵消的两式是互相等价的}\\ &\le\sum_{u\in S}\sum_{v\in T}f(u,v)&f(v,u)\ge 0\\ &\le\sum_{u\in S}\sum_{v\in T}c(u,v)&f(u,v)\le c(u,v)\\ &=||S,T||&\text{定义}\\ \end{aligned}$

对于第一个不等号，取等需要满足 $\forall u\in S,v\in T,f(v,u)=0$，即 $(v,u)$ 均空流。

对于第二个不等号，取等需要满足 $\forall u\in S,v\in T,f(u,v)=c(u,v)$，即 $(u,v)$ 均满流。

定理证明

$1\implies 2$

因为若残量网络 $G_f$ 上存在增广路，必然可以对其增广，使流量更大，与条件“$f$ 为最大流”矛盾。

$2\implies 3$

设 $S$ 为所有从 $s$ 出发能到达的点，$T=V-S$，则

• 对于 $u\in S,v\in T$，所有边 $(u,v)$ 均满流。分类讨论：
  否则其剩余容量 $c_f(u,v)=c(u,v)-f(u,v)>0$，有 $(u,v)$ 在 $G_f$ 上，可以从 $s\to u\to v$，与 $v\in T$ 矛盾。

• 同样的，对于 $u\in S,v\in T$，所有边 $(v,u)$ 均空流。

  否则其反向边 $(u,v)$ 的剩余容量 $c_f(u,v)=f(v,u)>0$，有 $(u,v)$ 在 $G_f$ 上，可以从 $s\to u\to v$，与 $v\in T$ 矛盾。

以上证明假定 $(u,v)\in E$ 和 $(v,u)\in E$。如果不满足此条件，则由定义默认 $f(u,v)=c(u,v)=0$、$f(v,u)=c(v,u)=0$，定理也是对的。而一种更 不 优美的方式是，

$c_f(u,v)={\color{red}\Big(c(u,v)-f(u,v)\Big)}+{\color{blue}f(v,u)}+{\color{green}0}=0$

我们将 $c_f(u,v)$ 定义中的三种可能相加。不管 $(u,v)\in E$、$(v,u)\in E$、$\text{otherwise}$，可以发现 除了满足的条件所对应的那一项，另外的两项均为 $0$。也就是说，上式符合定义。又由于 $c(u,v)-f(u,v)\ge 0,f(v,u)\ge 0$，故 $c(u,v)-f(u,v)=0,f(v,u)=0$。

所以不管怎么说，我们证明了引理中的取等条件，有我们构造的割 $(S,T)$ 满足 $|f|=||S,T||$。

$3\implies 1$

由于对于所有流 $f$、割 $(S,T)$ 都有 $|f|\le ||S,T||$，故取等时 $f$ 为最大流，$(S,T)$ 为最小割。

换句话说，若存在流 $f'$ 满足比 $f$ 流量更大，则 $|f'|>|f|=||S,T||$，与引理 $|f'|\le ||S,T||$ 矛盾。故不存在 $f'$，即 $f$ 为最大流。$(S,T)$ 为最小割同样可以用这种反证法证明。

$\square$

定理应用

那么这个定理有什么用？

1. Ford-Fulkerson 增广结束时，所得 $f$ 为最大流，即证明了该算法正确性；
2. 同时，证明了最大流流量等于最小割容量，即 $\max |f|=\min ||S,T||$；
3. 可得，我们同样可以使用 Ford-Fulkerson 求出最小割。

事实上，最大流最小割本质上是线性规划对偶。

费用流

定义

一条边单位流量的 费用（$w(u,v)$） 为一个 $V\times V\to\Bbb{R}$ 的函数，表示边 $(u,v)$ 流过 $f(u,v)$ 的流量需要花费 $f(u,v)\times w(u,v)$ 的费用。

最小费用最大流问题，即在最大流的前提下最小化每条边的费用之和 $\sum_{(u,v)\in E}f(u,v)\times w(u,v)$。

SSP 算法

SSP 算法（Successive Shortest Path Algorithm），即每次寻找费用和最小的增广路进行增广，也就是将最大流算法中的 bfs 改成了最短路算法。一般使用 EK + 队列优化 Bellman-Ford 实现。使用 Dinic 复杂度没有优化。

费用存在负环时 SSP 算法无法正确求解最小费用最大流问题，这种情况做题时一般也不会出现，这里先不讲，以后有时间再补解决方法。

代码

类似的，我们可以写出 SSP 算法的代码。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <bitset>

using std::cin;
typedef long long ll;
constexpr int N=5e3+1145,INF=0x3f3f3f3f;

namespace ssp
{
	int n,s,t;
	struct edge{int v,w,c;};
	std::vector<int> e[N];
	std::vector<edge> es;
	inline void add(int u,int v,int w,int c)
	{
		e[u].push_back(es.size());
		es.push_back({v,w,c});
		e[v].push_back(es.size());
		es.push_back({u,0,-c});
	}
	int dis[N],flow[N],pre[N];
	std::bitset<N> inq;
	bool exbf() // 队列优化 Bellman-Ford
	{
		std::fill(dis,dis+n+1,INF);
		dis[s]=0;
		flow[s]=INF;
		flow[t]=0;
		std::queue<int> q;
		q.push(s);
		int u,v,w,c;
		while(!q.empty())
		{
			u=q.front(),q.pop();
			inq[u]=false;
			for(int i=0;i<int(e[u].size());i++)
			{
				v=es[e[u][i]].v,w=es[e[u][i]].w,c=es[e[u][i]].c;
				if(w&&dis[v]>dis[u]+c)
				{
					dis[v]=dis[u]+c;
					flow[v]=std::min(w,flow[u]);
					pre[v]=e[u][i];
					if(!inq[v])q.push(v),inq[v]=true;
				}
			}
		}
		return flow[t];
	}
	int maxflow,mincost;
	void main() // EK
	{
		while(exbf())
		{
			maxflow+=flow[t];
			for(int u=t;u!=s;u=es[pre[u]^1].v)
			{
				es[pre[u]].w-=flow[t],es[pre[u]^1].w+=flow[t];
				mincost+=es[pre[u]].c*flow[t];
			}
		}
	}
} // namespace ssp

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m;
	cin>>ssp::n>>m>>ssp::s>>ssp::t;
	for(int i=1,u,v,w,c;i<=m;i++)
	{
		cin>>u>>v>>w>>c;
		ssp::add(u,v,w,c);
	}
	ssp::main();
	printf("%d %d",ssp::maxflow,ssp::mincost);
	return 0;
}

应用

二分图

最大匹配

P3386 【模板】二分图最大匹配

考虑建立最大流模型。

建立超级汇点 $s$ 连向所有左部点 $u\in V_0$，所有右部点 $v\in V_1$ 连向超级汇点 $t$。

上述边和原二分图中的边（只从左部连向右部）的容量均为 $1$。直接跑 Dinic 即可。

最小点覆盖 & 最大独立集

后记——拓展阅读

• [教程]网络流详解: 从入门到放弃
• Algorithms by Jeff Erickson