网络流

网络

网络和网络流是不一样的。(废话，毕竟他俩差一个字)

网络是指一个有向图 \(G = (V, E)\)，每条边 \((u, v) \in E\) 都有一个权值 \(c(u, v)\)，我们把它叫做这条边的容量。

显然，当 \((u, v) \notin E\) 时，\(c(u, v) = 0\)。

其中有 \(2\) 个特殊的点：源点 \(s\) 和汇点 \(t\)，\(s,t \in V\) 且 \(s \not= t\)。

流

我们设 \(f(u, v)\) 为定义在二元组 \((u \in V, v \in V)\) 上的实数函数，则当它满足以下 \(3\) 个条件时就被称为网络 \(G\) 的流函数。

• 容量限制：对于每条边，流量不超过容量，即 \(f(u, v) \le c(u, v)\)。

• 斜对称性：每条边的流量与其相反边的流量互为相反数，即 \(f(u, v) = -f(v, u)\)。

• 流守恒性：流出源点的流量一定等于流入汇点的流量，即 \(\forall x \not= s, x \not= t,\sum_{(u, x) \in E} f(u, x) = \sum_{(x, v) \in E} f(x, v)\)。

这个时候对于 \((u, v) \in E\)，我们称 \(f(u, v)\)，为边的流量，\(c(u, v) - f(u, v)\) 为边的剩余容量。整个网络的流量为 \(\sum_{(s, v) \in E} f(s, v)\) 。

常见问题

一般使用网络流解决最大流，最小割，费用流，上下界网络流 \(4\) 种。

最大流

显然，对于一个网络 \(G\)，合法的流函数有很多很多。所以我们要去求它的最值，最小值肯定是 \(0\)，而最大值则是我们接下来要详细讲的最大流。

使 \(\sum_{(s, x) \in E} f(s, x)\) 最大的流函数被称为网络的最大流，此时流量被称为网络的最大流。

FF（Ford-Fulkerson）

这个算法运用贪心的方法，通过不断在残量网络中寻找增广路实现。

增广路就是指在残量网络中存在一条路径 \(P\)（\(P\) 为边集），使 \(\forall (u, v) \in P, r(u, v) > 0\) （\(r(u, v) = c(u, v) - f(u, v)\)，为剩余容量）。

注：只要残量网络中还存在增广路，说明一定还有一些流量可以从源点流到汇点，故此时还没有找到最大流。

而这个算法正是通过 dfs 寻找当前残量网络中的增广路，此增广路的流为 \(min(r(u, v))\)。

注：这里一定是最小，因为如果流量大于最小剩余容量的话就一定存在至少一条边无法正常流过。

找到一条增广路增加答案后，就对增广路上的每一条边和每一条反向边进行修改。

假设此增广路流为 \(flow\)，若 \((u, v) \in P\)，\(r'(u, v) = r(u, v) - flow\)，根据斜对称性：\(r'(v, u) = r(v, u) + flow\)。

修改反向边是必不可少的，因为我们不能保证当前增广路都是最优的。如果不进行此操作，可能会导致接下来源点与汇点不再联通，但实际上如果当前增广路换一种可以避免这个问题。

直到残量网络中 \(s\) 与 \(t\) 不在联通时，算法结束，得到最大流。

注意：用链式前向星存图 \(tot\) 必须从 \(1\) 开始（即第一条边编号为 \(2\)），因为更新反边是通过 \(i \oplus 1\)，第输入的第 \(i\) 条边编号为 \(2i - 1\)，反向边 \(2i\)，但 \((2i - 1) \oplus 1 = 2i- 2\)，而不是 \(2i\)，这样就会导致错误。

struct node {
   int n, m, head[N], tot, flow;
   bool vis[N];
   Edge edge[M << 1];
   inline node() { tot = 1; }
   inline void add(int u, int v, int c) {
     edge[++tot].c = c, edge[tot].to = v;
     edge[tot].next = head[u], head[u] = tot;
   }
   inline int dfs(int u, int flow, int t) {
   	if (u == t)
   		return flow;
   	vis[u] = true;
   	for (int i = head[u]; i; i = edge[i].next) {
   		int v = edge[i].to, c = edge[i].c, flo;
   		if (c && !vis[v]) //如果当前边还可以继续流并且还没有流过当前点 
   			if (~(flo = dfs(v, min(flow, c), t))) {	//求出流，如果不是-1代表找到增广路 
   				edge[i].c -= flo, edge[i ^ 1].c += flo;	//修改增广路上每一条边及其反向边 
   				return flo;
   			}
   	}
   	vis[u] = false;	//回溯 
   	return -1;
   } 
   inline void FF(int s, int t) {
   	flow = 0;
   	int f;
   	while (~(f = dfs(s, inf, t))) {	//寻找增广路 
   		flow += f; //将答案加上当前增广路的流 
   		for (int i = 1; i <= n; i++)
   			vis[i] = false;
   	}
   }
} F;

时间复杂度：\(O(nm^2)\)。

EK(Edmonds–Karp)

其实就是对 FF 优化了一下。

可以看到，FF 使用 dfs 寻找增广路，如果到达 \(t\) 说明找到一条增广路，并在回溯的时候修改每条增广路上边以及对应反向边的剩余容量。

但 dfs 的复杂度很高，所以 FF 算法非常容易超时，我们考虑优化一下。

而 EK 算法就是将 FF 算法的 dfs 改为 bfs 寻找增广路，这样降低了程序的时间复杂度。

整个算法实现过程如下：

• 若从 \(s\) 找到了一条到 \(t\) 的增广路，就说明还可以继续更新答案。

• 对于增广路上每一个点（除 \(s\) 外），用 \(pre_i\) 记录从编号为 \(pre_i\) 的边到达 \(i\) 这个点。

• 修改每条增广路上的边及其反向边的剩余容量。

• 重复以上过程直到 \(s\) 与 \(t\) 不连通。

注：\(tot\) 仍要从 \(1\) 开始。