「学习笔记」网络流

「学习笔记」网络流

点击查看目录

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

\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;
		}
	};
}

例题

[SCOI2007] 蜥蜴

拆点后成板子题。

[SDOI2015] 星际战争

二分时间,然后建二分图,在激光武器和巨型机器人之间连容量为无限的边。

源点到激光武器容量为时间乘攻击力,巨型机器人到汇点容量为装甲值。

如果最大流等于总装甲值说明合法。

注意精度问题,建议乘 \(10000\)

士兵占领

最少很难求,于是转化为每个格都放了士兵之后,最多能去掉多少个士兵。

源点向代表每一行的点连边,容量为这一行最多能删除的士兵数量,列同理。

如果某一个点无障碍,则将其所属行和所属列连边。

[HNOI2007] 紧急疏散EVACUATE

二分时间,然后把一个门拆成多个门,代表不同时间。

然后就比较好想了,但是不好预处理。

[SDOI2009] 晨跑

费用流板子题。

[SDOI2016] 数字配对

比较重要的一个性质是,如果 \(a_i\)\(a_j\) 可以配对,那么两者质因数个数刚好相差一。

那么可以根据质因数个数奇偶性建出二分图然后跑费用流。

[SCOI2007] 修车

发现这个费用很难计算啊。

但是我们有拆点!谁说只能拆成出入点的?

你把第 \(i\) 个师傅拆成 \(j\) 个师傅,其中的第 \(k\)\(i\) 号师傅表示这个师傅倒数第 \(k\) 次修车,这个时候花费用的时间要乘 \(k\),因为后面修的 \(k-1\) 车都会被这次耽误。

然后跑一个费用流。

[NOI2012] 美食节

和修车差不多,但是交上去会发现 T 了!怎么回事呢?

点太多了。

你发现一次用不到很多点,所以你考虑动态加点,一个师傅被增广过就给他再拆一个点。

[AHOI2009] 最小割

首先根据证明最大流最小割定理的过程,可行边必须满流。

然后你发现如果残量网络中仍有 \(u\)\(v\) 的路径则 \((u, v)\) 也不是可行边,因为砍了没用。

剩下都是可行边。

然后发现若残量网络 \(S\) 能到 \(u\)\(v\) 能到 \(T\),那么边 \((u, v)\) 是一条必经边。

否则经过这条边的增广路径上还会有与这条边容量一样的边,割掉后效果相同。

考虑跑 Tarjan 后使用 SCC 判定连通。

热门相关:都市御魔人   仙府之缘   都市御魔人   初体验3   帝国远征