「学习笔记」网络流

2023-10-27 17:15 由 K8He 发表于 #其他

「学习笔记」网络流

点击查看目录

目录
「学习笔记」网络流
知识点
一些基础定义
最大流
Ford-Fulkerson 算法（增广路算法）
Edmonds-Karp 算法
Dinic 算法
最小割
费用流
EK 费用流
ZKW 费用流
例题
[SCOI2007] 蜥蜴
[SDOI2015] 星际战争
士兵占领
[HNOI2007] 紧急疏散EVACUATE
[SDOI2009] 晨跑
[SDOI2016] 数字配对
[SCOI2007] 修车
[NOI2012] 美食节
[AHOI2009] 最小割

定义部分名词括号内写个英文是为了方便起函数名变量名。

\rvalue/\rvalue/\rvalue/\rvalue/\rvalue/

仅提供大致思路，想看详细点的看上面链接。

建议学的时候自己多手画几个图模拟一下。

常见建模套路，打算以后单开一个博写，因为还有好多套路没有学。

知识点

一些基础定义

主要来自 OI-wiki。

「网络（Flow Network）」：指一张有向图 \(G = (V, E)\)。
「容量（Capacity）」：在一个网络中，对于每一组边 \((u, v) \in E\) 都有一个权值 \(c(u, v)\) 被称为容量。若 \((u, v) \not\in E\) 则 \(c(u, v) = 0\)。
「源点（Source）与汇点（Sink）」：两种存在于网络中的比较特殊的点，所有流从源点 \(s(s\in V)\) 流出，最后流入汇点 \(t(t\in V)\)，\(s\neq t\)。
「流（Flow）」：若函数 \(f(u, v)\) 满足以下三点性质：
1. 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 \(f(u,v)\leq c(u,v)\)。
2. 斜对称性：每条边的流量与其相反边的流量之和为 0，即 \(f(u,v)=-f(v,u)\)。
3. 流守恒性：从源点流出的流量等于汇点流入的流量，即 \(\sum_{(s, u)\in E}f(s,u)=\sum_{(u, t)\in E}f(u,t)\)。
则 \(f\) 是网络 \(G\) 的流函数。

对于每一条边 \((u, v)\in E\)，\(f(u, v)\) 被称为边 \((u, v)\) 的「流量」，\(c(u, v) - f(u, v)\) 被称为边 \((u, v)\) 的「剩余流量」。

所有流从源点 \(s(s\in V)\) 流出，因此整个网络流量为 \(\sum_{(s, u)\in E}f(s,u)\)。

最大流

「最大流（Max-flow）」：给定一个网络，求一个流函数使这个网络的总流量最大。

Ford-Fulkerson 算法（增广路算法）

「增广路（Augmenting Path）」：一条起点为源点，终点为汇点的剩余流量不为空的边的路径。

这里的增广路与二分图中的不是一个，但是是一个思想。

考虑不断从源点出发寻找增广路并将其跑满，但是这样是错的，因为你增广出来的不一定是最优解里需要的，考虑使这个操作「可撤销」。

解决办法是建立反向边，原来的边流量减多少反向边加多少（流的斜对称性），可以把原来的边上不优的流通过反向边推到另一条边上。

下图是从 OI-wiki 拿的，可以感性理解一下：

但是这玩意复杂度保证不了啊！有可能会出现下图这种情况（from rvalue）：

graph LR; s-->|23333333|1 1-->|23333333|t 1-->|1|2 2-->|23333333|t s-->|23333333|2

可能会出现流在容量为 \(1\) 的那条边被反复推的情况，这个时候复杂度就取决于值域了。

Edmonds-Karp 算法

简称 EK 算法。

考虑每次找增广路时找最短的增广路。这个直接 01 最短路找，时间复杂度 \(O(E)\)。

不难发现这样找到的增广路长度单调不减，最长为 \(V\)，那么考虑迭代次数即可算出时间复杂度。

每次跑增广路都会有一条边流量被跑满，我们称这样的边为「关键边」。每次跑增广路都会出现一条关建边，那么所有边成为「关键边」次数之和即为迭代次数。一条边成为关键边之后暂时会从图中消失，再次出现必须跑其反向边，这时增广路长度必然增加，那么每条边最多 \(V\) 会成为「关键边」，总迭代次数是 \(VE\) 次。

因此总时间复杂度是 \(O(VE^2)\)。

感觉还是不够快，观察发现原因是每次最短的增广路有很多条，但是每次只增广一条。

继续优化。

Dinic 算法

思考如何一次性把所有最短增广路跑了。

按与源点的距离建立分层图，然后跑一遍 DFS 把全图的最短路跑满。

乍一看感觉层数严格递增，DFS 遍历所有点，复杂度是 \(O(VE)\) 的，但是 DFS 中一个点会重复经过所以不能保证其复杂度。

考虑两个优化：

无用点优化
如果有流量流向一个点的时候这个点流不动了，说明它在当前分层图上不再能做出贡献，可以暂时删去。
当前弧优化
决定复杂度，不会负优化，你慢了说明你挂了。
如果当前到点 \(u\) 的流在 \(u\) 遍历完其指向的所有点时用完了，我们记录一下是推向哪条边时用完的，下次再搜索到 \(u\) 时直接从这条边开始推，因为之前的肯定推满了。

考虑计算时间复杂度。

参考 EK 算法时间复杂度的证明，每次找增广路最多找 \(E\) 条，长度最多为 \(V\)，分层图层数严格递增，最多会建 \(V\) 次分层图，时间复杂度上限为 \(O(V^2E)\)。

注意到计算复杂度时用词都是「最多」，稍微想一想就会发现不可能跑满，这个复杂度上限是非常松的，一般出题人不会卡你，卡了也没关系，因为这样干就不会有什么人能过题了。

下面是一份实现：

namespace GRAPH {
	class Edge { public: ll v, w, r; };
	class Graph {
	private:
		ll n, s, t, c[N][N];
		std::vector <Edge> tu[N];
	public:
		inline void Init (ll _n, ll _s, ll _t) { 
			n = _n, s = _s, t = _t;
			return;
		}
		inline void AddEdge (ll u, ll v, ll w) {
			c[u][v] += w;
			ll p1 = tu[u].size (), p2 = tu[v].size ();
			tu[u].push_back ((Edge){v, w, p2});
			tu[v].push_back ((Edge){u, 0, p1});
			return;
		}
	private:
		ll dep[N], cur[N];
	public:
		ll maxflow;
	private:
		inline bool DinicBFS () {
			memset (dep, 0, sizeof (dep));
			std::queue <ll> q;
			q.push (s), dep[s] = 1, cur[s] = 0;
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				far (p, tu[u]) {
					if (!p.w || dep[p.v]) continue;
					dep[p.v] = dep[u] + 1, cur[p.v] = 0;
					if (p.v == t) return true;
					q.push (p.v);
				}
			}
			return false;
		}
		inline ll DinicDFS (ll u, ll flow) {
			if (u == t || flow <= 0) return flow;
			ll sum = 0, sz = tu[u].size () - 1;
			for (ll &i = cur[u]; i <= sz; ++i) {
				Edge &p = tu[u][i];
				if (!p.w || dep[p.v] != dep[u] + 1) continue;
				ll k = DinicDFS (p.v, std::min (flow, p.w));
				if (k <= 0) dep[p.v] = 0;
				p.w -= k, tu[p.v][p.r].w += k;
				sum += k, flow -= k;
				if (flow <= 0) break;
			}
			return sum;
		}
	public:
		inline void Dinic () {
			maxflow = 0;
			while (DinicBFS ()) maxflow += DinicDFS (s, inf);
			return;
		}
	};
}

最小割

删去一些边，使得 \(s\) 与 \(t\) 不连通，求这些边的最小容量和。

形式化一点：

「割（Cut）」：将网络 \(G\) 分为 \(S\) 和 \(T = V - S\) 两个点集，满足 \(s\in S, t\in T\)，则称 \((S, T)\) 为 \(G\) 的一个割。
「割的容量（Cut capacity）」：对于网络 \(G\) 的一个割 \((S, T)\)，其容量 \(c(S, T)\) 为 \(\sum_{u \in S, v \in T, (u, v)\in E}c(u, v)\)。
「最小割（Min-cut）」：求一个割 \((S, T)\)，使 \(c(S, T)\) 最小。

最大流最小割定理：最大流等于最小割的容量。

稍加思考还是比较好想到证明的。

跑最大流时跑满容量的边全割掉就是一个合法的割了，如果割完后图还联通就说明还有增广路，那就不是最大流了。既然这已经是一种合法的割了那最小割就不可能大于最大流。

如果最小割小于最大流，显然割掉的边是必由之路，应该割掉的边跑满了之后没有增广路了，那就不可能有更多的流流到汇点，假设不成立。

不大于也不小于就只能等于了呗。

费用流

「费用（Cost）」：每条边新增一个权值「费用」，即 \(1\) 单位的流经过这条边所需的费用。单位为 \(a\) 的流经过一条费用和为 \(b\) 的路径所需费用为 \(a\times b\)。
「最小费用最大流（Min-cost max-flow）」：满足流最大的前提下使费用最小。

EK 费用流

仍使用 EK 算法的思路，但是在求最短路的过程，边长度不再是 \(0/1\)，而是费用。

注意反向边费用为负，原因考虑反向推流的过程。

ZKW 费用流

Dinic 求分层图换成 SPFA 即可。

但一个比较恶心的事情是，这样不能当前弧优化，无法保证复杂度。

但是上界依然很松，所以随便用！

一份实现：

const ll N = 1e5 + 10, inf = 1ll << 40;

namespace GRAPH {
	class Edge {
	public:
		ll v, w, c, r;
	};
	class Graph {
	private:
		ll n, s, t;
		std::vector <Edge> tu[N];
	public:
		inline void Init (ll _n, ll _s, ll _t) { n = _n, s = _s, t = _t; return; }
		inline void AddEdge (ll u, ll v, ll w, ll c) {
			ll p1 = tu[u].size (), p2 = tu[v].size ();
			tu[u].push_back ((Edge) { v, w, c, p2 });
			tu[v].push_back ((Edge) { u, 0, -c, p1 });
			return;
		}
	private:
		ll dis[N]; bool vis[N];
	public:
		ll maxflow, mincost;
	private:
		inline bool SPFA () {
			memset (vis, 0, sizeof (vis));
			memset (dis, 0x3f, sizeof (dis));
			std::queue <ll> q;
			q.push (s), dis[s] = 0, vis[s] = true;
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				far (p, tu[u]) {
					if (!p.w || dis[u] + p.c >= dis[p.v]) continue;
					dis[p.v] = dis[u] + p.c;
					if (!vis[p.v]) q.push (p.v), vis[p.v] = 1;
				}
				vis[u] = false;
			}
			return dis[t] < inf;
		}
		inline ll DFS (ll u, ll flow) {
			if (u == t || flow <= 0) return flow;
			ll sum = 0; vis[u] = true;
			far (&p, tu[u]) {
				if (!p.w || dis[p.v] != dis[u] + p.c || vis[p.v]) continue;
				ll k = DFS (p.v, std::min (flow, p.w));
				sum += k, flow -= k;
				p.w -= k, tu[p.v][p.r].w += k;
				if (flow <= 0) break;
			}
			return sum;
		}
	public:
		inline void Dinic () {
			maxflow = mincost = 0;
			while (SPFA ()) {
				ll f = DFS (s, inf);
				maxflow += f, mincost += f * dis[t];
			}
			return;
		}
	};
}