网络流简述

本文将从简要介绍网络流的定义，最大流和最小割之间的关系，并使用C++实现EK算法和Dinic算法。本文还会简单地介绍费用流。部分定义和论证过程可能不够严谨，仅助于理解，严谨的定义和证明过程请在参考资料中查阅。

网络流相关定义

例子

我们在讨论定义之前，先看一个例子。

假设我们得到了一个城市的所有下水管道的数据，这份数据的表示方法为：以交叉水管口为节点（二叉口、三叉口…），以交叉口之间的边为链接节点之间的边，建立一个有向图。每段水管有各自的最大水流量，假设这个城市只有一个出水口排水到城市外。你想知道，在离你家最近的那个水管交叉口注水，注水的流量极大，足够长时间后那个出水口的流量是多少。

网络流定义

对于一个有向图$G=(V,E)$，有一个源点$s$（source）和一个汇点$t$（sink），$(s\not = t)$。每条边都可以流过一定流量（flow），每条边都有其容量$c$（capacity），代表流过的流量不能超过$c$，对于一个网络中非源点且非汇点的节点$u$，流入的流量等于流出的流量。

这个有源点和汇点并且具有容量的有向图就是网络（network）。

s-t割定义

在有向图$G=(V,E)$中，点集$S$包含源点$s$，点集$T$包含汇点$t$，那么$S\cap T=\empty$ 且$S\cup T=V$，则$\{S,T\}$称为$G$的一个$s-t$割（cut）。

$s-t$割的大小为点集$S$到点集$T$的所有边的容量之和。

最大流和最小割

从连通性到不相交路径

先讨论下面这样的问题。

对于有向图$G=(V,E)$，有不同的两点$s$和$t$，从$s$到$t$的路径是否存在。

这个问题是一个连通性问题，我们只需要找到一条从$s$到$t$的路径即可，使用并查集，DFS，BFS，Floyd等算法都可以实现。

如果将上述问题修改一下。

对于有向图$G=(V,E)$，有不同的两点$s$和$t$，是否存在两条从$s$到$t$的不相交路径。

不相交路径指的是一条路径与另一条路径没有相同边，可以有相同节点。

我们先设想使用暴力算法解决，枚举所有可能的路径，将每一条路径和其他路径对比是否有公共边，这样的时间复杂度为$O(E^3)$。

第一个问题可以看作是否存在一条不相交路径，那么这样拓展，我们可以提出一个一般性的问题。

对于有向图$G=(V,E)$，有不同的两点$s$和$t$，是否存在$n$条从$s$到$t$的不相交路径。

如果我们仍然使用暴力算法，每次枚举所有边，要么加入该边，要么不加入该边，时间复杂度为$O(2^E)$，只适用于$E$在很小的时候，并不高效。

我们可以把这个一般性的问题转化为另一个问题，即求不相交路径的最大数量，如果这个最大数大于等于$n$的话就肯定存在，反之则不存在那么多条。

所以这个问题转化为了一个求最值的问题。

对于有向图$G=(V,E)$，有不同的两点$s$和$t$，从$s$到$t$的不相交路径最多有多少条。

那么如何求解这个问题呢？更准确地说，如何使用一个多项式时间复杂度的算法来求解这个问题呢？

有的兄弟，有的。

Ford–Fulkerson 增广

下文会先给出算法的流程，再解释其正确性。

上述的最值问题中，有向图$G=(V,E)$中，$s$称为源点，$t$称为汇点，从源点到汇点的一条路径称为增广路（Augmenting Path）。

我们使用这样的算法（初始记录值为0）：

1. 寻找一条增广路，并且记录路径，若找不到就结束。
2. 找到一条增广路后，将该路径上的所有边反向，记录值加1。
3. 回到步骤1，继续寻找增广路。

其中将边反向这个操作的名称为“构建残余网络”，修改过后的这个有向图称为“残余网络”。

这样的算法叫做Ford–Fulkerson 增广，使用了贪心的思想。

下面的图示展现了算法是如何进行的。

下面我们尝试去理解这个算法。

不相交路径和最小割

（以下证明过程为个人方法，更加严谨过程请参见参考资料）

在一个$s-t$割中，所有的路径都会通过这个割，即任意路径中存在一条从节点$u$到节点$v$的边$(u,v)$，$u\in S$且$v\in T$。

所以可知不相交路径数肯定不超过任何一个$s-t$割的大小（这里大小指的是点集$S$到点集$T$有多少条边）。

最小的$s-t$割大小称为最小割。不相交路径数小于等于最小割。

假设我们已经找到了最小割，并且我们知道相应的点集$S$和$T$。完成所有不相交路径的选择后，如果一条边没有被通过，有四种情况：第一种情况是从$s$不能到达该边，即该边的起点与源点不连通；第二种情况是该边的终点与$t$不连通；第三种情况是该边的起点和终点都不与$s$和$t$；第四种情况是该边起点和终点与$s$和$t$均连通，但该边所在的所有路径与其他已选择的路径有相同边。

假设最大不相交路径数小于最小割，那么在这个割中，必然会有一条边$(u,v)$使得其不在已选择的不相交路径中，设已选择不相交路径的形成的边集为$A$。若是第一种情况，将与该边起点连通的所有点划分至$T$；若是第二种或第三种情况，将与该边终点连通的所有点划分至$S$。这三种情况做调整后都会使得割变小，与最小割矛盾，所以只出现第四种情况，该边所在的任意一条路径与其他已选择的路径相同路径为起点为$k$终点为$l$，所以节点$k$的入度至少为2，节点$l$的出度至少为2，并且不难得到$k$所有能够到达$t$的出边所在路径必定经过$l$，所有能够从$s$到达$l$的入边所在路径必定经过$k$，不然则不满足最大不相交路径数。将点集$S$和$T$重新划分，其余点不变，将所有$s$到$k$的路径上的点划分至$S$，将所有$l$到$t$的路径上的点划分至$T$，由于不经过$k$和$l$路径上的点所在点集不变，这样割的大小仍然为最小割，而割中减少了一条不在边集$A$中的边。在新形成的最小割上再次如上述重新划分直至割上所有边都在$A$中，使得最大不相交路径等于最小割，与假设的情况矛盾。

所以最大不相交路径数等于最小割。

反向建边的正确性

所以我们又将问题转化为了求解最小割。

网络上的资料大多都是从“反悔”操作角度解释，也就是走反向边和原先正向边抵消从而达成“反悔”。这里我给出一个从最小割角度的解释。

由于我们找到一条增广路就将路径上的边反向，所以最小割的大小必定会减1。新构建的残余网络上的最小割大小相比与构建此次残余网络前一次的最小割大小少1。这样反复直到不存在增广路时结束，即最小割为0时结束。重复寻找增广路的次数就是原最小割的大小。

为什么需要将路径上所有的边反向呢？是因为不知道最小割如何划分，但是必然这条增广路会经过最小割。

这样就可以得到最小割的大小，从而得到最多有多少条不相交路径，从而解决上面的问题了。

求解最大流

将有向图中的重边合并，两点之间重边的数量计为容量，我们就得到了一个网络。求解流量最大问题（最大流问题）就是求解最大不相交路径数的问题。

这篇文章开头的例子，就是求解最大流。

下面介绍两种求解最大流的算法，都是基于Ford–Fulkerson 增广实现的。

Edmonds–Karp 算法

Edmonds–Karp 算法简称EK算法。具体思路为：使用BFS寻找增广路，再将增广路反向。

这里包含两个细节：

1. 在初始建边时，正向边流量设置为初始流量，反向边流量设置为0，一般成对设置，正向边编号为奇数，反向边编号为偶数。

2. 反向建边可以看作将正向边流量退掉$\Delta$，反向边流量加上$\Delta$。

下面是EK算法的C++实现，图储存采用邻接表实现。

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

const int inf = 1e9 + 7;

struct edge
{
	int v, c, nx;
};

edge e[20007];
int mxf[1007], pre[1007], h[1007], ecnt;	// mxf[i]代表节点i的输入流量，pre记录路径
int n, m, s, t, maxflow;

int bfs()
{
	memset(mxf, 0, sizeof(mxf));
	int u, v, c;
	queue <int> q;
	q.push(s), mxf[s] = inf;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		if (u == t)
			return 1;
		for (int i = h[u]; i != -1; i = e[i].nx)
		{
			v = e[i].v, c = e[i].c;
			if (mxf[v] == 0 && c)
			{
				mxf[v] = min(mxf[u], c);
				pre[v] = i;
				q.push(v);
			}
		}
	}
	return 0;
}

void add(int u, int v, int w)
{
	e[ecnt].nx = h[u];
	e[ecnt].v = v;
	e[ecnt].c = w;
	h[u] = ecnt;
	++ ecnt;
}

int main()
{
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= n; ++ i) h[i] = -1;
	for (int i = 1, u, v, w; i <= m; ++ i)
	{
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, 0);
	}
	while (bfs())			// bfs寻找增广路，找不到就说明增广路寻找
	{
		int v = t;
		while (v != s)		// 反向边
		{
			int i = pre[v];
			e[i].c -= mxf[t];
			e[i ^ 1].c += mxf[t];
			v = e[i ^ 1].v;
		}
		maxflow += mxf[t];	// 更新最大流
	}
	cout << maxflow;
	return 0;
}

单轮BFS时间复杂度为$O(E)$，增广总轮数上界为$O(VE)$，所以EK算法的时间复杂度为$O(VE^2)$，详细且严谨的证明过程请参见参考资料。

Dinic 算法

Dinic算法相较于EK算法效率更高，时间复杂度更低。

Dinic算法可以理解为在BFS建立分层图并检查是否存在增广路径后，使用DFS寻找多条增广路（多路增广）建立反向边。

DFS带来的多路增广有四个细节：

1. 搜索顺序优化，分层图限制了搜索深度
2. 当前弧优化，剪枝。本轮分层图下，使得此次DFS寻找结束后，下一次DFS走到该节点时直接从保存的边开始
3. 剩余流量优化，剪枝。流入的流量使用完就退出
4. 残枝优化，剪枝。如果这个节点流不出任何流量至汇点，直接剪枝

下面是Dinic算法的C++实现，图储存采用邻接表实现。

#include <iostream>
#include <queue>
#include <cstring>
#define LL long long
using namespace std;

const LL inf = 1e17 + 7;

struct edge
{
	LL v, c, nx;
} e[20007];

LL n, m, s, t;
LL d[1007], h[1007], cur[1007], cnt, maxflow;// d代表分层图上的的深度，cur[u]储存当前点的出边

void add(LL u, LL v, LL w)
{
	e[cnt] = {v, w, h[u]};
	h[u] = cnt;
	cnt ++;
}

int bfs()
{
	memset(d, 0, sizeof d);
	int u, v, c;
	queue <int> q;
	q.push(s), d[s] = 1;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		if (u == t) return 1;
		for (int i = h[u]; i != -1; i = e[i].nx)
		{
			v = e[i].v, c = e[i].c;
			if (d[v] == 0 && c)
			{
				d[v] = d[u] + 1;	// 建立分层图
				q.push(v);
			}
		}
	}
	return 0;
}

LL dfs(LL u, LL mf)
{
	if (u == t) return mf;
	LL sum = 0, v, c, flow;
	for (int i = cur[u]; i != -1; i = e[i].nx)
	{
		cur[u] = i;	// 当前弧优化
		v = e[i].v, c = e[i].c;
		if (d[v] == d[u] + 1 && c)
		{
			flow = dfs(v, min(mf, c));
			e[i].c -= flow;	// 退流操作
			e[i ^ 1].c += flow;
			sum += flow;
			mf -= flow;
			if (mf == 0) break;	// 剩余流量优化
		}
	}
	if (sum == 0) d[u] = 0;	// 残枝优化
	return sum;
}


int main()
{
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= n; ++ i) h[i] = -1;
	for (int i = 1, u, v, w; i <= m; ++ i)
	{
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, 0);
	}
	
	while (bfs())	// 建立分层图和检查增广路
	{
		memcpy(cur, h, sizeof h);	// 每轮分层图初始化cur
		maxflow += dfs(s, inf);	// 更新最大流
	}
	cout << maxflow;
	return 0;
}

Dinic算法中单轮DFS的时间复杂度为$O(VE)$，增广轮数是$O(V)$，所以Dinic算法的时间复杂度为$O(V^2E)$，详细严谨的分析证明过程请参见参考资料。

其他算法

求解最大流的算法还有MAM算法、ISAP、Push-Relabel 预流推进算法、HLPP算法等，本文不涉及这些算法，详细请参见参考资料。

最大流问题实例

Luogu P3376

给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入第一行包含四个正整数 $n,m,s,t$，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来 $m$ 行每行包含三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，边权为 $w_i$（即该边最大流量为 $w_i$）。

输出一行，包含一个正整数，即为该网络的最大流。

输入

>4 5 4 3
4 2 30
>4 3 20
2 3 20
>2 1 30
1 3 30

输出

50

保证 $1 \leq n\leq200$，$1 \leq m\leq 5000$，$0 \leq w\lt 2^{31}$。

使用上述提供的EK算法和Dinic算法示例都可以通过该题。

Luogu P2756

第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

一共有 $n$ 个飞行员，其中有 $m$ 个外籍飞行员和 $(n - m)$ 个英国飞行员，外籍飞行员从 $1$ 到 $m$ 编号，英国飞行员从 $m + 1$ 到 $n$ 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 $m$ 和飞行员总数 $n$。
从第二行起到倒数第二行，每行有两个整数 $u, v$，代表外籍飞行员 $u$ 可以和英国飞行员 $v$ 配合。
输入的最后一行保证为 -1 -1，代表输入结束。

本题存在 Special Judge。
请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是 $k$。
第 $2$ 行到第 $k + 1$ 行，每行输出两个整数 $u, v$，代表在你给出的方案中，外籍飞行员 $u$ 和英国飞行员 $v$ 配合。这 $k$ 行的 $u$ 与 $v$ 应该互不相同。

输入

5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

输出

4
1 7
2 9
3 8
5 10

• 对于 $100\%$ 的数据，保证 $1 \leq m \leq n < 100$，$1 \leq u \leq m < v \leq n$，同一组配对关系只会给出一次。

二分图匹配问题，可以使用匈牙利算法实现，这里可以使用最大流算法。先构建网络，建立超级源点和超级汇点，超级源点连接一侧节点，超级汇点连接另一侧节点，边容量设置为1即可。

下面使用Dinic算法实现。

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

const int inf = 1e9 + 7;

struct edge
{
	int v, c, nx;
} e[20007];

int m, n;
int h[107], d[107], cur[107], cnt, vis[107], maxflow;

void add(int u, int v, int w)
{
	e[cnt] = {v, w, h[u]};
	h[u] = cnt ++;
}

int bfs()
{
	memset(d, 0, sizeof d);
	int u, v, c;
	queue <int> q;
	q.push(0), d[0] = 1;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		if (u == n + 1) return 1;
		for (int i = h[u]; i != -1; i = e[i].nx)
		{
			v = e[i].v, c = e[i].c;
			if (d[v] == 0 && c)
			{
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int dfs(int u, int mf)
{
	if (u == n + 1) return mf;
	int sum = 0, v, c, flow;
	for (int i = cur[u]; i != -1; i = e[i].nx)
	{
		cur[u] = i;
		v = e[i].v, c = e[i].c;
		if (d[v] == d[u] + 1 && c)
		{
			flow = dfs(v, min(mf, c));
			e[i].c -= flow;
			e[i ^ 1].c += flow;
			sum += flow;
			mf -= flow;
			if (mf == 0) break;
		}
	}
	if (sum == 0) d[u] = 0;
	return sum;
}

int main()
{
	cin >> m >> n;
	for (int i = 0; i <= n; ++ i) h[i] = -1;
	while (1)
	{
		int u, v;
		cin >> u >> v;
		if (u == -1 && v == -1) break;
		add(u, v, 1), add(v, u, 0);
		if (!vis[u]) vis[u] = 1, add(0, u, 1), add(u, 0, 0);
		if (!vis[v]) vis[v] = 1, add(v, n + 1, 1), add(n + 1, v, 0);
	}
	
	while (bfs())
	{
		memcpy(cur, h, sizeof h);
		maxflow += dfs(0, inf);
	}
	cout << maxflow << '\n';
	for (int i = 1; i < cnt; i += 2)
	{
		if (e[i].v != 0 && e[i].v != n + 1 && e[i ^ 1].v != 0 && e[i ^ 1].v != n + 1
			&& e[i].c)
			cout << e[i].v << ' ' << e[i ^ 1].v << '\n';
	}
	return 0;
}

Luogu P2754

由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。

现有 $n$ 个太空站位于地球与月球之间，且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而太空船的容量是有限的，第 $i$ 艘太空船只可容纳 $h_i$ 个人。每艘太空船将周期性地停靠一系列的太空站，例如 $(1,3,4)$ 表示该太空船将周期性地停靠太空站 $134134134\dots$。每一艘太空船从一个太空站驶往任一太空站耗时均为 $1$。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

输入的第一行是三个用空格隔开的整数，分别代表太空站个数 $n$，太空船个数 $m$ 和地球上的人数 $k$。

第 $2$ 到第 $(m + 1)$ 行，每行给出一艘太空船的信息，第 $(i + 1)$ 行的第一个整数 $h_i$ 代表第 $i$ 艘太空船可容纳的人数。随后有一个整数 $r_i$，代表第 $i$ 艘太空船停靠的站点数。之后有 $r_i$ 个整数，依次代表该太空船停靠站点的编号 $S_{i, j}$，其中太空站自 $1$ 至 $n$ 编号，地球编号为 $0$，月球编号为 $-1$。

输出一行一个整数，代表将所有人转移到月球上的最短用时。若无解则输出 $0$。

输入

2 2 1
1 3 0 1 2
1 3 1 2 -1

输出

5

对于 $100\%$ 的数据，保证：

• $1 \leq n \leq 13$。
• $1 \leq m \leq 20$。
• $1 \leq k \leq 50$。
• $1 \leq r_i \leq n + 2$。
• $-1 \leq S_{i, j}\leq n$。

此题需要对网络进行建模，若一个时间对应最大流恰好大于总人数，则这个时间就是最短用时，所以需要求解每个时间的最大流。根据时间依次建点和边，即每天以该天每条船到达的空间站建立新的点，前一天的空间站与该天建边，容量为相应空间船的容量，由于可以停留且容量无限，所以为每个点建立一个自环，容量为无限大。建立超级源点和超级汇点，超级源点都流入地球节点，容量为无限大；月球节点都流入汇点，容量无限大。使用并查集检查连通性。

于是这样建模完成，使用Dinic算法求解。

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

const int inf = 1e9 + 7;

struct edge
{
	int v, c, nx;
} e[100007];

int n, m, s = 0, t, k, ss = 30005, tt = 30006;
int h[30007], d[30007], cur[30007], cnt, maxflow;
int hh[107], r[107];
int fa[107];
vector <int> ship[107];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void add(int u, int v, int w)
{
	e[cnt] = {v, w, h[u]};
	h[u] = cnt ++;
}

int bfs()
{
	memset(d, 0, sizeof d);
	int u, v, c;
	queue <int> q;
	q.push(ss), d[ss] = 1;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		for (int i = h[u]; i != -1; i = e[i].nx)
		{
			v = e[i].v, c = e[i].c;
			if (d[v] == 0 && c)
			{
				d[v] = d[u] + 1;
				q.push(v);
				if (v == tt) return 1;
			}
		}
	}
	return 0;
}

int dfs(int u, int mf)
{
	if (u == tt) return mf;
	int sum = 0, v, c, flow;
	for (int i = cur[u]; i != -1; i = e[i].nx)
	{
		cur[u] = i;
		v = e[i].v, c = e[i].c;
		if (d[v] == d[u] + 1 && c)
		{
			flow = dfs(v, min(mf, c));
			e[i].c -= flow;
			e[i ^ 1].c += flow;
			sum += flow;
			mf -= flow;
			if (mf == 0) break;
		}
	}
	if (sum == 0) d[u] = 0;
	return sum;
}

int main()
{
	cin >> n >> m >> k;
	t = n + 1;
	memset(h, -1, sizeof h);
	for (int i = 0; i <= 20; ++ i) fa[i] = i;
	for (int i = 1; i <= m; ++ i)
	{
		cin >> hh[i] >> r[i];
		for (int j = 1, sta; j <= r[i]; ++ j)
		{
			cin >> sta;
			ship[i].push_back(sta);
		}
	}
	for (int i = 0; i < 1000; ++ i)
		for (int j = 0; j <= n + 1; ++ j)
		{
			add(j + i * (n + 2), j + (i + 1) * (n + 2), inf),
			add(j + (i + 1) * (n + 2), j + i * (n + 2), 0);
			if (j == s)
				add(ss, s + i * (n + 2), inf),
				add(s + i * (n + 2), ss, 0);
			if (j == n + 1)
				add(t + i * (n + 2), tt, inf),
				add(tt, t + i * (n + 2), 0);
		}
	
	int tm = 0;
	while (++ tm)
	{
		for (int i = 1; i <= m; ++ i)
		{
			int lst = ship[i][(tm - 1) % r[i]], now = ship[i][tm % r[i]];
			if (lst == -1) lst = t;
			if (now == -1) now = t;
			add(lst + ((tm - 1) * (n + 2)), now + (tm * (n + 2)), hh[i]), add(now + (tm * (n + 2)), lst + ((tm - 1) * (n + 2)), 0);
			if (find(lst) != find(now))
				fa[now] = lst;
			while (bfs())
			{
				memcpy(cur, h, sizeof h);
				maxflow += dfs(ss, inf);
			}
		}
		if (maxflow >= k) break;
		if (tm > 50)
		{
			for (int i = 0; i <= n; ++ i)
				find(i);
			find(t);
			for (int i = 0; i <= n; ++ i)
				if (fa[i] != fa[0])
				{
					cout << 0;
					return 0;
				}
			if (fa[t] != fa[0])
			{
				cout << 0;
				return 0;
			}
		}
	}
	cout << tm;
	return 0;
}

层次化结构和局部动态扩展的网络建模使得EK算法和Dinic算法在图上效率更高，使实际运行效率优于理论最坏情况。

费用流

下面将简单介绍费用流，本文不涉及费用流的代码实现和原理解释（之后可能会补上），仅作了解，详细请参见参考资料。

在网络中，一条边加上单位流量费用就成为了费用流。求解的问题一般为最大流下花费的最小费用（最小费用最大流）。

SSP 算法

Successive Shortest Path 算法，简称SSP算法，利用贪心的思想，每次寻找最短路径增广路（单位费用最小的增广路）增广，直到找不到增广路为止。若存在负环，则要先消去负环。

一般会使用SPFA来寻找增广路，而不是Dijkstra（处理不了负权）。

Primal-Dual 原始对偶算法

为了使用Dijkstra，类似与Johnson 全源最短路径算法，对每个点设置势能，将边权设置为非负。

ZKW 费用流

由OI选手ZKW提出的类似原始对偶算法的一种基于最短路径增广的费用流算法。使用反向SPFA初始化距离估计值（类似与势函数），使用了当前弧优化的多路增广以及动态更新标号使得其效率较高。

三种费用流算法对比

下面给出一个表格，对比了三种费用流算法的效率。

算法	时间复杂度（理论）	稀疏图效率	稠密图效率	负权处理	代码复杂度
原始对偶（Dinic+Dijkstra）	$O(F \cdot (E + V \log V))$	高	最优	通过势函数消除负权	中等
连续最短路（SPFA）	$O(F \cdot VE)$	低	低	直接处理	低
ZKW费用流	$O(F \cdot (E + V \log V))$	最优	中等	反向SPFA初始化	低

参考资料

1. OI Wiki（最大流等于最小割，时间复杂度及费用流等的详细严谨证明）
2. [算法竞赛入门] 网络流基础：理解最大流/最小割定理 (蒋炎岩)
3. 董晓算法
4. DeepSeek提供的关于费用流的资料