1. 一些基本定义
网络
网络是指一个有向图 \(G=(V,E)\)。
每条边 \((u,v)\in E\) 都有一个权值 \(c(u,v)\)，称之为容量（Capacity），当 \((u,v)\notin E\) 时有 \(c(u,v)=0\)。
其中有两个特殊的点：源点（Source）\(s\in V\) 和汇点（Sink）\(t\in V,(s\neq t)\)。
流
设 \(f(u,v)\) 定义在二元组 \((u\in V,v\in V)\) 上的实数函数且满足
- 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即，\(f(u,v)\leq c(u,v)\)
- 斜对称性：每条边的流量与其相反边的流量之和为 0，即 \(f(u,v)=-f(v,u)\)
- 流守恒性：从源点流出的流量等于汇点流入的流量，即 \(\forall x\in V-\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)\)
那么 \(f\) 称为网络 \(G\) 的流函数。对于 \((u,v)\in E\)，\(f(u,v)\) 称为边的 流量，\(c(u,v)-f(u,v)\) 称为边的 剩余容量。整个网络的流量为 \(\sum_{(s,v)\in E}f(s,v)\)，即 从源点发出的所有流量之和。
一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述三个性质。
2. 最大流
有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。
2.1 增广
解决最大流问题的算法使用了 不断寻找增广路 和 能流满就流满 的贪心思想。
具体的说，我们每次在残量网络 \(G_f\) 上找到一条增广路 \(P\)，并使 \(P\) 上的每一条边都流过增广路上剩余流量最小的边的流量。但是这样做，我们该如何保证正确性呢？
此时需要加入 反悔机制，我们在为当前边 \((u,v)\) 加上流量 \(c\) 时，同时给其反边 \((v,u)\) 的容量加上 \(c\)，这样做是为了使我们能够进行反悔操作。使得我们能够收回一部分流量。这样的过程称为一次 增广。
2.2 最大流最小割定理
网络流中有一个十分重要的理论：最大流等于最小割。
证明作者不会，后续补上。
2.3 Dinic算法
2.3.1 算法介绍
Dinic 算法的核心是建出 分层图，然后只在 相邻层之间增广。
其中建出分层图采用 bfs 实现，而寻找增广路采用 dfs 实现。
在 dfs 时我们限制流量只从当前层流向下一层，并进行 多路增广，过程中我们需要维护当前节点和剩余流量。
Dinic 算法有一个十分重要的优化是 当前弧优化。 如果有一条边 \((u, v)\) 已经满流，即流量与容量相等，那么我们在这一轮增广中显然没有必要再去尝试对 \((u, v)\) 进行增广，可以直接跳过。因此对于每个点，我们记录从该点出发第一个还没有满流的边，称为 当前弧，文中记为 \(cur_i\)。我们每次搜索到一个点，便直接从该点的当前弧进行增广。
特别需要注意的一点是，每一轮多路增广之前 \(cur_u\) 都需要重置为点 \(u\) 的邻接表头，因为一条边在一次增广中满流并不代表它后续不会被收回流量。仍然有可能重新出现在残量网络中。
使用当前弧优化和多路增广后的 Dinic 算法最坏时间复杂度为 \(O(n^2m)\)，但实际应用中远远达不到这个上界。
2.3.2 时间复杂度证明
证明作者不会，后续补上。
3. 无负环的费用流
费用流一般指 最小费用最大流。
费用流相较于一般的网络流，在每条边上添加了一个额外的费用 \(w\)。而最小费用最大流要求我们在保证 最大流 的前提下，求出一种费用最少的方案。
3.1 SSP算法
3.1.1 算法介绍
SSP（Successive Shortest Path）算法是一个贪心的算法。它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。
需要注意的是，SSP 无法解决图中存在负环的情况，这时需要更进阶的技巧，这里不做介绍。
实现 SSP 只需要我们把 EK 或者 Dinic 的 bfs 增广改为 SPFA 求最短路即可。
一般 SSP 采用基于 EK 的形式实现，时间复杂度 \(O(nmf)\)，其中 \(f\) 为最大流流量，实际应用远远达不到这个上界，可以放心使用。
学长的建议：SPFA 一定要手写队列，不然会很难受。（个人觉得现在的比赛开 O2 用 STL 应该问题不大）
模板题 P3381 最小费用最大流 代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, inf = 1e9;
int tot = 1;
struct Edge {
int nxt, y, z, w;
} e[N];
int n, m, S, T;
int head[N], dis[N], flow[N];
inline void addedge(int x, int y, int z, int w)
{
e[++tot] = (Edge) {head[x], y, z, w};
head[x] = tot;
}
inline void add(int x, int y, int z, int w)
{
addedge(x, y, z, w);
addedge(y, x, 0, -w);
}
int pre[N], vis[N];
inline bool spfa()
{
queue<int> q;
memset(dis, 0x3f, sizeof(dis));
dis[S] = 0; flow[S] = inf; flow[T] = 0;
q.push(S);
while(!q.empty())
{
int x = q.front(); q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = e[i].nxt)
{
int y = e[i].y, z = e[i].z, cost = e[i].w;
if(!z || dis[y] <= dis[x] + cost) continue;
dis[y] = dis[x] + cost;
flow[y] = min(z, flow[x]);
pre[y] = i;
if(!vis[y]) q.push(y), vis[y] = 1;
}
}
return flow[T];
}
int maxflow, mincost;
inline void update()
{
maxflow += flow[T];
for(int x = T; x != S; x = e[pre[x] ^ 1].y)
{
e[pre[x]].z -= flow[T]; e[pre[x] ^ 1].z += flow[T];
mincost += flow[T] * e[pre[x]].w;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> S >> T;
for(int i = 1; i <= m; i++)
{
int x, y, z, w;
cin >> x >> y >> z >> w;
add(x, y, z, w);
}
while(spfa())
update();
cout << maxflow << ' ' << mincost;
return 0;
}
- 关于最大费用最大流： 我们在连边时直接将费用取反跑最小费用最大流，这样跑出来的最小费用再进行取反就是原图的最大费用了。
例题 P4014 分配问题 代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, inf = 1e9;
int n, c[105][105];
struct Edge {
int nxt, y, z, w;
};
struct Graph {
int tot = 1, head[305];
Edge p[N];
inline void addedge(int x, int y, int z, int w) {
p[++tot] = (Edge) {head[x], y, z, w};
head[x] = tot;
}
inline void add(int x, int y, int z, int w) {
addedge(x, y, z, w);
addedge(y, x, 0, -w);
}
} e, E;
int S, T;
int dis[N], vis[N], pre[N], flow[N];
inline bool spfa()
{
memset(dis, 0x3f, sizeof(dis));
queue<int> q; dis[S] = 0;
q.push(S); flow[S] = inf; flow[T] = 0;
while(!q.empty())
{
int x = q.front(); q.pop();
vis[x] = 0;
for(int i = e.head[x]; i; i = e.p[i].nxt)
{
int y = e.p[i].y, z = e.p[i].z, cost = e.p[i].w;
if(!z || dis[y] <= dis[x] + cost) continue;
dis[y] = dis[x] + cost;
pre[y] = i; flow[y] = min(z, flow[x]);
if(!vis[y]) q.push(y), vis[y] = 1;
}
}
return flow[T];
}
int mincost;
inline void update()
{
for(int x = T; x != S; x = e.p[pre[x] ^ 1].y)
{
mincost += flow[T] * e.p[pre[x]].w;
e.p[pre[x]].z -= flow[T]; e.p[pre[x] ^ 1].z += flow[T];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n; S = 2 * n + 1; T = S + 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> c[i][j];
for(int i = 1; i <= n; i++) {
e.add(S, i, 1, 0);
e.add(i + n, T, 1, 0);
E.add(S, i, 1, 0);
E.add(i + n, T, 1, 0);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
e.add(i, j + n, 1, c[i][j]);
E.add(i, j + n, 1, -c[i][j]);
}
while(spfa()) update();
cout << mincost << '\n';
e = E; mincost = 0;
while(spfa()) update();
cout << -mincost;
return 0;
}
3.1.2 证明
证明作者不会，后续补上。
4.网络流 24 题（鸽）
\(^*\)A. P1251 餐巾计划问题
神秘题目，思想十分奇妙。
这题需要我们一反常规思路，首先拆点，将一天拆为早上和晚上。
显然，每天晚上一定会得到 \(r_i\) 块脏毛巾，这启发我们由源点向每天晚上的点连一条容量为 \(r_i\)，费用为 \(0\) 的边。
对于一块毛巾，我们可以选择延期送洗，快洗或慢洗。
对于延期送洗，我们由当天晚上向下一天晚上连一条容量为 \(\infty\)，费用为 \(0\) 的边，而快洗就由当天晚上向 \(m\) 天后的早上，容量为 \(\infty\)，费用为 \(f\) 的边。慢洗同理。
然后对于每天早上，我们要么买毛巾，要么用洗过的毛巾。洗毛巾的情况在上面已经讨论，买毛巾只需要我们由源点向每天早上的点连一条容量为当天所需毛巾条数，费用为 \(p\) 的边就行。
最后我们由每天早上代表的点向汇点连出容量为当天毛巾所需条数，费用为 \(0\) 的边。跑一遍最小费用最大流即可。
B. P2754 [CTSC1999] 家园 / 星际转移问题
提取题目要素：时间、站点、人。
考虑把人看成流，根据时间和站点来建图。
对于第 \(i\) 个单位时间，每艘太空船都会转移到它的安排中的下一个站点，因此我们由第 \(i\) 秒该艘太空船所处的站点出发，向太空船下一刻到达的站点连一条容量为太空船可容纳人数的边。
然后对于每个太空站，它的状态可以继承到下一个时刻，因此我们在第 \(i\) 个时刻，由第 \(j\) 个太空站向第 \(i + 1\) 个时刻的第 \(j\) 个太空站连一条容量为 \(\infty\) 的边。
同时记住特判地球和月亮的编号，最后枚举时间，不断在残量网络上跑最大流，当最大流的值大于等于人数时输出时间即可。
C. P2756 飞行员配对方案问题
二分图最大匹配模板，跑一遍最大流然后对于每个右部点检查一下流量来自哪个点就行。
用匈牙利更加方便并且自带方案。
D. P2761 软件补丁问题
注意到数据范围很小，因此能到达的状态一定不会太多，直接状压+SPFA即可。
E. P2762 太空飞行计划问题
鸽。