【模板】網路流（Flow）
===

## 網路流問題

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

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

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

而一個可行流，即是對於所有邊 $u,v$ 找到一個流量 $F(u,v)$ 滿足：

- 對一個節點 $u$，流進 = 流出： $\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 \rightarrow v$ 「填充」或「移除」流量 $2$，則在剩餘網路上會如此表現：


因此我們可以在剩餘網路上找一條 $s-t$ 路徑，其邊權皆至少為 $d$，然後把路徑上的邊都「填充」或「移除」流量 $d$，那我們就成功使最大流增加 $d$ 了。此路徑稱為增廣路徑。通常我們會使 $d$ 盡量大，使 $d$ 為這條路的瓶頸。

> 增廣路徑最大流定理：若圖是簡單的，且所有容量為非負整數：
若有可行流 $F$ 使得找不到增廣路徑 $\iff$ $F$ 為最大流
>

則根據上述定理，不斷找出增廣路徑，就能找到最大流。而每次找到的增廣路流量至少為 $1$，因此複雜度為 $O(VF)$。

找增廣路時使用 BFS，使得增廣路總是 $s-t$ 最短路，則為 Edmond-Karps 算法，複雜度 $O(E^2V)$。[證明參考](https://oi-wiki.org/graph/flow/max-flow/#edmondskarp-算法)。

### 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^2E)$。在邊權皆為一的圖上，大約是 $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';