【模板】網路流（Flow）

網路流問題

給定一張圖，每條邊有容量，給定源點、匯點，求從源點到匯點的最大流量。

上述為一個最大流問題。在一個網路流問題中，我們定義：

• 源點為
  $s$，匯點為
  $t$
• $F(u,v)$ 為
  $u$ 到
  $v$ 的流量
• $C(u,v)$ 為
  $u$ 到
  $v$ 的容量

而一個可行流，即是對於所有邊

$u,v$ 找到一個流量

$F(u,v)$ 滿足：

• 對一個節點
  $u$，流進 = 流出：
  $\mathrm{\forall }u\sum _{v\in in}F(v,u)=\sum _{v\in out}F(u,v)$
• 流量不超過容量：
  $F(u,v)\le C(u,v)$

Ford–Fulkerson Algorithm（最大流演算法）

要找最大流，我們可以不斷找一條尚未飽和的路徑，將其填充流量，直到找不到為止。但這樣會造成「路徑阻塞的問題」。考慮以下網路：

由於直接找路徑填充流量會造成阻塞，我們還需要「回推」錯誤的流。回推一條邊的流

$F(u,v)$，也是幫

$v$ 找到新的流量來源，幫

$u$ 找到新的流量，使得在移除

$u,v$ 的流量時，還能維持

$u,v$ 的進出總量不變。

建構一個剩餘網路： 對於一個可行流，我們使

$R(u,v)=C(u,v)-F(u,v)$，

$R(v,u)=F(u,v)$。直白的解釋，對於一條邊的容量，我們在剩餘網路蓋一條正向邊，表示剩餘的容量；再蓋一條反向邊，代表已經使用的容量，因此

$R(u,v)+R(v,u)=C(u,v)$。

假設有

$F(u,v)=2,C(u,v)=6$，則

$R(u,v)=4,R(v,u)=2$：

若要對

$u\to v$ 「填充」或「移除」流量

$2$，則在剩餘網路上會如此表現：

因此我們可以在剩餘網路上找一條

$s-t$ 路徑，其邊權皆至少為

$d$，然後把路徑上的邊都「填充」或「移除」流量

$d$，那我們就成功使最大流增加

$d$ 了。此路徑稱為增廣路徑。通常我們會使

$d$ 盡量大，使

$d$ 為這條路的瓶頸。

增廣路徑最大流定理：若圖是簡單的，且所有容量為非負整數：
若有可行流

$F$ 使得找不到增廣路徑

$⟺$

$F$ 為最大流

則根據上述定理，不斷找出增廣路徑，就能找到最大流。而每次找到的增廣路流量至少為

$1$，因此複雜度為

$O(VF)$。

找增廣路時使用 BFS，使得增廣路總是

$s-t$ 最短路，則為 Edmond-Karps 算法，複雜度

$O(E^{2}V)$。證明參考。

Dicnic

Dicnic 算法思想：

因為要找可行的增廣路徑，因此剩餘網路

$G_r$，只保留那些

$R(u,v)>0$ 的邊。接著從源點

$s$ BFS 得到每個點

$u$ 的最短距離

$lev[u]$ 並依此做分層，使得節點

$u$ 只能連向

$lev[v]=lev[u]+1$ 的節點

$v$。稱分層後的圖

$G_L$ 為「層次圖」。

在層次圖

$G_L$ 上找到一個最大增廣流（可以有分支）

$f_b$，稱為「阻塞流」。

Dicnic 算法流程如下：

1. 在
   $G_r$ 上 BFS 出層次圖
   $G_L$（途中要略過
   $R(u,v)=0$ 的邊）
2. 在層次圖上找到阻塞流
   $f_b$
3. 將
   $f_b$ 併入原先的流
   $f$，即
   $f\leftarrow f+f_b$
4. 重複直到在
   $G_r$ 上
   $s-t$ 不連通（
   $G_r$ 上的任一條
   $s-t$ 路徑使得瓶頸
   $>0$ 都是增廣路）

在 Dicnic 結束後，不存在

$s-t$ 路徑，不管怎麼走都會遇到一條邊

$(u,v)$ 使得

$R(u,v)=0$。其意義為流量已經流滿。在剩餘網路上的特徵，是源點可以走到

$u$ 但不可走到

$v$。這條邊即為割邊。

Dicnic 的複雜度為

$O(V^{2}E)$。在邊權皆為一的圖上，大約是

$O(VE\times min(V^{2/3},E^{1/2}))$。做二分圖匹配時，複雜度為

$O(E\sqrt{V})$。

/**
 * Description: Fast flow. After computing flow, edges $\{u,v\}$ such that 
	* $lev[u] \neq -1,$ $lev[v] = -1$ are part of min cut.
	* Use \texttt{reset} and \texttt{rcap} for Gomory-Hu.
 * Time: $O(N^2M)$ flow, $O(M\sqrt N)$ bipartite matching, $O(NM\sqrt N) or $O(NM\sqrtM) on unit graph.
 */
struct Dinic {
	using F = ll; // flow type
	struct Edge { int to; F flo, cap; };
	int N; V<Edge> eds; V<vi> adj;
	void init(int _N) { N = _N; adj.rsz(N), cur.rsz(N); }
	/// void reset() { each(e,eds) e.flo = 0; }
	void ae(int u, int v, F cap, F rcap = 0) { assert(min(cap,rcap) >= 0); 
		adj[u].pb(sz(eds)); eds.pb({v,0,cap});
		adj[v].pb(sz(eds)); eds.pb({u,0,rcap});
	}
	vi lev; V<vi::iterator> cur;
	bool bfs(int s, int t) { // level = shortest distance from source
		lev = vi(N,-1); F0R(i,0,N) cur[i] = begin(adj[i]);
		queue<int> q({s}); lev[s] = 0; 
		while (sz(q)) { int u = q.front(); q.pop();
			for (auto &e: adj[u]) { const Edge& E = eds[e];
				int v = E.to; if (lev[v] < 0 && E.flo < E.cap) 
					q.push(v), lev[v] = lev[u]+1;
			}
		}
		return lev[t] >= 0;
	}
	F dfs(int v, int t, F flo) {
		if (v == t) return flo;
		for (; cur[v] != end(adj[v]); cur[v]++) {
			Edge& E = eds[*cur[v]];
			if (lev[E.to]!=lev[v]+1||E.flo==E.cap) continue;
			F df = dfs(E.to,t,min(flo,E.cap-E.flo));
			if (df) { E.flo += df; eds[*cur[v]^1].flo -= df;
				return df; } // saturated >=1 one edge
		}
		return 0;
	}
	F maxFlow(int s, int t) {
		F tot = 0; while (bfs(s,t)) while (F df = 
			dfs(s,t,numeric_limits<F>::max())) tot += df;
		return tot;
	}
};

signed main() {
    roadroller
}

費用流

若流量有每單位收費，即邊

$(u,v)$ 有流量

$f(u,v)$ 則必須收取

$f(u,v)\times w(u,v)$，則為費用流。費用流的思想是在每次尋找增廣路徑時，總是找花費最低的。做 Edmond-Kaprs 或 Dicnic 時改成最短路即可。

struct MCMF {
	using F = ll; using C = ll; // flow type, cost type
	struct Edge { int to; F flo, cap; C cost; };
	int N; V<C> p, dist; vi pre; V<Edge> eds; V<vi> adj;
	void init(int _N) { N = _N; // vertex: [0, _N)
		p.rsz(N), dist.rsz(N), pre.rsz(N), adj.rsz(N); }
	void add_edge(int u, int v, F cap, C cost) {
		assert(cap >= 0); assert(0 <= u && u <= _N); assert(0<=v && v <= _N);
		adj[u].pb(sz(eds)); eds.pb({v,0,cap,cost});
		adj[v].pb(sz(eds)); eds.pb({u,0,0,-cost});
	} // use asserts, don't try smth dumb
	bool path(int s, int t) { // find lowest cost path to send flow through
		const C inf = numeric_limits<C>::max(); F0R(i,0,N) dist[i] = inf;
		using T = pair<C,int>; priority_queue<T,vector<T>,greater<T>> todo;
		todo.push({dist[s] = 0,s});
		while (sz(todo)) { // Dijkstra
			T x = todo.top(); todo.pop(); if (x.ff > dist[x.ss]) continue;
			for (auto &e: adj[x.ss]){ const Edge& E = eds[e]; // all weights should be non-negative
				if (E.flo < E.cap && cmin(dist[E.to],x.ff+E.cost+p[x.ss]-p[E.to]))
					pre[E.to] = e, todo.push({dist[E.to],E.to});
			}
		} // if costs are doubles, add some EPS so you
		// don't traverse ~0-weight cycle repeatedly
		return dist[t] != inf; // return flow
	}
	pair<F,C> calc(int s, int t) { assert(s != t);
		F0R(_,0,N) F0R(e,0,sz(eds)) { const Edge& E = eds[e]; // Bellman-Ford
			if (E.cap) cmin(p[E.to],p[eds[e^1].to]+E.cost); }
		F totFlow = 0; C totCost = 0;
		while (path(s,t)) { // p -> potentials for Dijkstra
			F0R(i,0,N) p[i] += dist[i]; // don't matter for unreachable nodes
			F df = numeric_limits<F>::max();
			for (int x = t; x != s; x = eds[pre[x]^1].to) {
				const Edge& E = eds[pre[x]]; cmin(df,E.cap-E.flo); }
			totFlow += df; totCost += (p[t]-p[s])*df;
			for (int x = t; x != s; x = eds[pre[x]^1].to)
				eds[pre[x]].flo += df, eds[pre[x]^1].flo -= df;
		} // get max flow you can send along path
		return {totFlow,totCost};
	}
};

網路流應用

最大流最小割

$s-t$ 割：把節點劃分為兩個集合

$S,T$，其中

$s\in S,t\in T$，便是割。若邊

$(u,v)$ 橫跨兩個集合，則屬於該割的割集

$X_C$。而

$s-t$ 割的容量為所有割集中的邊的權重和，即

$c=\sum _{(u,v)\in X_C}w(u,v)$。

不嚴謹地說，割即為圖的一個斷面。畫一條線割開

$s$ 和

$t$ 使得

$s,t$ 不連通，線經過的邊即為割集。（如果在一條邊經過經過線偶數次，那麼它不屬於割集）。

最小割即為所有割中容量最小的，**也就是是在求

$s$ 到

$t$ 中流量最小的斷面。**容易相信，上面這個敘述跟最大流是等價，因此最大流和最小割是相同的問題。題目要求最小割集時，因為最小割集即是最大流流量瓶頸，因此在 Dicnic 時一旦找到最大流，那些

$(u,v)$ 使得一邊可從

$u$ 到達、一邊不可則屬於割集。總結而言，以下三件是等價：

• $f$ 為最大流
• 剩餘網路
  $G_r$ 不存在增廣路徑
• $|f|$ 為最小割

匹配、最小覆蓋、最大獨立

名詞定義：

• 最大邊獨立集（最大匹配）：最大的邊集，使得沒有邊共用同一個點
• 最小邊覆蓋：最小的邊集，每個點都被至少一個邊覆蓋
• 最大點獨立集（最大獨立集）：最大的點集，使得沒有點共用同一個邊（沒有點相鄰）
• 最小點覆蓋：最小的點集，使得每個邊都至少被一個點覆蓋

要注意的是最大匹配（maximum matching）和極大匹配（maximal matching）不同，極大匹配指的是沒辦法直接加入其他邊，已經達到飽和的情況。

有以下性質：

• 點數 = 最大邊獨立集 + 最小邊覆蓋
• 點數 = 最大點獨立集 + 最小點覆蓋

對於二分圖還有：

• 最大邊獨立集 = 最小點覆蓋（最小邊覆蓋 = 最大點獨立集）

而二分圖的最大匹配可以用 Dicnic 求。二分圖帶權最大匹配則可以用 MCMF 求。

DAG 的最小路徑覆蓋：

DAG 的最小「不相交」路徑覆蓋可以轉成二分圖最大匹配來求，而最小「可相交」路徑覆蓋可以轉成不相交來求。

DAG 最小不相交路徑覆蓋：
將點

$x$ 拆成

$x_{in},x_{out}$ ，若有邊

$u\to v$ ，則在新圖建邊

$u_{out}\to v_{in}$ 。新圖為二分圖，且最小不相交路徑覆蓋 =

$|V|-$ 新圖最大匹配。

證明：
一開始每個點都是一個路徑，每當選擇一個邊將就可以把兩個路徑首尾相連，即所需路徑數量減一。因此我們要求最大的邊集。但路徑不能相交，即一個點不能同時有一個以上的出度或入度，因此我們將入度和出度拆開，其中每個入度或出度都只能被一條邊覆蓋。因此新圖最大匹配即是路徑減少的數量。

DAG 最小相交路徑覆蓋：

若點

$x$ 可以走到

$y$，則建邊

$x\to y$。

考慮

$A\to B,B\to C,D\to B,B\to E$。路徑可以相交，即可能會出現

$A\to B\to C$ 和

$D\to B\to E$ 想同時存在，則此時讓第二條路徑直接略過

$B$ ，走

$D\to E$ 即可。

常見網路流模型整理

最大權閉合子圖：

• TIOJ 2128 . 殿壬發大財

拆點：

• Luogu 1231. 教辅的组成

附註

• Reference

  • https://oi-wiki.org/graph/flow/max-flow/
  • https://slides.com/sylveon/graph-7#/16
  • https://docs.google.com/presentation/d/1wWFF-71pj0oNgwQi9QOJOoBQV_iMlfv7LKi-XDVpAls/edit#slide=id.g11baa5fcc4a_0_33
  • https://blog.csdn.net/vocaloid01/article/details/81083071
  • https://www.cnblogs.com/justPassBy/p/5369930.html

• Template

  ​​​​#include <bits/stdc++.h>
  ​​​​#include <ext/pb_ds/assoc_container.hpp>
  ​​​​using namespace std;
  ​​​​using namespace __gnu_pbds;
  ​​​​typedef long long ll;
  ​​​​
  ​​​​typedef pair<int, int> pii;
  ​​​​#define mp make_pair
  ​​​​#define ff first
  ​​​​#define ss second
  ​​​​
  ​​​​#define V vector
  ​​​​#define sz(a) ((int)a.size())
  ​​​​#define all(v) (v).begin(), (v).end()
  ​​​​#define rall(v) (v).rbegin(), (v).rend()
  ​​​​#define pb push_back
  ​​​​#define rsz resize
  ​​​​typedef V<int> vi;
  ​​​​
  ​​​​#define FOR(i,j,k) for (int i=(j); i<=(k); i++)
  ​​​​#define F0R(i,j,k) for (int i=(j); i<(k); i++)
  ​​​​
  ​​​​ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
  ​​​​ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }
  ​​​​
  ​​​​#define roadroller ios::sync_with_stdio(0), cin.tie(0);
  ​​​​#define de(x) cout << #x << '=' << x << ", "
  ​​​​#define dd cout << '\n';