【圖論】網絡流算法入門

（決定狠狠加訓圖論了，從一直想學但沒啟動的網絡流算法開始。）

網絡流問題

? 問題定義：在帶權有向圖 $G = (V, E)$ 中，每條邊 $e = (u, v)$ 有容量 $c (u, v)$ ，求從源點 $s$ 到匯點 $t$ 的最大流量。

1. 最大流 = 最小割定理

? 最小割的定義：
割（Cut）是將圖 $G$ 的頂點分為兩個不相交集合 $S$ 和 $T$ ，其中 $\in S$ ， $\in T$ 。
割的容量是 所有從 $S$ 到 $T$ 的邊的容量之和，即： $\text{容量}(S, T) = \sum_{u \in S, v \in T} c(u, v)$
? 最大流-最小割定理：
在任何網絡中，最大流的值等于最小割的容量。
直觀理解：
? 流量受限于網絡中“最窄的瓶頸”，即最小割的容量。
? 最大流無法超過任何割的容量，而存在至少一個割的容量等于最大流。

? 證明思路：

弱對偶性：最大流 ≤ 最小割（顯然成立）。
強對偶性：通過構造殘留網絡，證明存在一個割的容量等于最大流。
當算法終止時，殘留網絡中 $s$ 能到達的頂點集合 $S$ ，其余為 $T$ ，此時 $S$ 到 $T$ 的邊流量飽和，容量等于最大流。

2. 殘留網絡與反向邊

? 殘留網絡 $G_f$ ：
? 對每條邊 $e = (u, v)$ ，定義其反向邊 $e^{'} = (v, u)$ ，容量為當前流量 $f (u, v)$ 。
? 殘留容量：
$c_f(u, v) = c(u, v) - f(u, v), \quad c_f(v, u) = f(u, v)$
? 作用：允許“退回”流量，尋找更優路徑。

? 增廣路徑：
在殘留網絡 $G_f$ 中找到一條從 $s$ 到 $t$ 的路徑，路徑上的最小殘留容量稱為 增廣量。
通過增加該路徑的流量，逐步逼近最大流。

3. 費用流問題

? 問題定義：
在最大流問題的基礎上，每條邊 $e = (u, v)$ 有一個單位流量費用 $w (u, v)$ ，求在最大流的前提下，總費用最小的流。

? 關鍵思想：
? 最小費用最大流：優先選擇費用最小的增廣路徑。
? 算法擴展：
? Successive Shortest Path (SSP)：每次用SPFA/Bellman-Ford找最短路增廣。
? Primal-Dual：結合Dijkstra和勢函數處理負權邊。
? Cost-Scaling：通過縮放費用值優化效率。

? 費用流的反向邊處理：
反向邊的費用為 $? w (u, v)$ ，表示退回流量時費用被抵消。

算法模板：

1. Dinic算法

? 原理：

分層圖：通過BFS構建層次圖（將節點按到源點的最短距離分層）。
阻塞流：在分層圖上用DFS找增廣路徑，并通過“當前弧優化”跳過無效邊。
多路增廣：允許一次DFS找到多條增廣路徑，減少遞歸次數。
? 時間復雜度： $O(n^2 m)$ ，實際表現優秀，適合大多數場景。
? 適用問題：最大流問題，在稠密圖和稀疏圖中均表現良好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;const int inf = 1e18;      // 表示無窮大的容量
const int maxn = 1e5 + 10; // 最大節點數// 邊的結構體
struct edge {int from, to; // 邊的起點和終點int cap;      // 邊的容量int flow;     // 邊當前的流量edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};// Dinic算法實現類
struct Dinic {int n, m;           // 節點數、邊數int s, t;           // 源點、匯點vector<edge> edges; // 所有邊的集合，邊數兩倍（包含反向邊）vector<int> G[maxn]; // 鄰接表，G[i]保存節點i的所有邊在edges中的索引bool vis[maxn]; // BFS使用的訪問標記數組int d[maxn];    // 層次網絡中各節點的層次（距離）int cur[maxn]; // 當前弧優化數組，記錄每個節點當前處理的邊void init(int n) { // 初始化，n為節點數this->n = n;for (int i = 0; i < n; i++)G[i].clear();edges.clear();}// 清空所有邊的流量，用于多次計算不同流的情況void clear() {for (int i = 0; i < edges.size(); i++)edges[i].flow = 0;}// 將邊的容量減去已使用的流量，用于調整殘余網絡void reduce() {for (int i = 0; i < edges.size(); i++)edges[i].cap -= edges[i].flow;}// 添加一條從from到to，容量為cap的有向邊及其反向邊void addedge(int from, int to, int cap) {edges.push_back(edge(from, to, cap, 0)); // 正向邊，初始流量0edges.push_back(edge(to, from, 0, 0)); // 反向邊，初始容量0，流量0m = edges.size();G[from].push_back(m - 2); // 記錄正向邊在edges中的索引G[to].push_back(m - 1);   // 記錄反向邊在edges中的索引}// BFS構建層次網絡，返回是否存在從s到t的路徑bool BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;Q.push(s); // 源點入隊vis[s] = true;d[s] = 0;while (!Q.empty()) {int x = Q.front();Q.pop();for (int i = 0; i < G[x].size(); i++) { // 遍歷x的所有鄰接邊edge &e = edges[G[x][i]];// 若邊的終點未訪問，且仍有剩余容量if (!vis[e.to] && e.cap > e.flow) {vis[e.to] = true;d[e.to] = d[x] + 1; // 層次+1Q.push(e.to);}}}return vis[t]; // 返回匯點是否可達}// DFS尋找增廣路徑，x為當前節點，a為當前路徑上的最小剩余容量int DFS(int x, int a) {if (x == t || a == 0) // 若到達匯點或剩余容量為0，直接返回return a;int flow = 0, f;// 使用當前弧優化，避免重復訪問已經處理過的邊for (int &i = cur[x]; i < G[x].size(); i++) {edge &e = edges[G[x][i]];// 層次遞增且存在剩余容量if (d[x] + 1 == d[e.to] &&(f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {e.flow += f;                  // 更新正向邊流量edges[G[x][i] ^ 1].flow -= f; // 反向邊流量減少（允許反向增廣）flow += f;                    // 累加到總流量a -= f;                       // 剩余容量減少if (a == 0)break; // 剩余容量為0，無需繼續搜索}}if (flow == 0)d[x] = -2; // 炸點優化return flow;}// 計算從s到t的最大流int Maxflow(int s, int t) {this->s = s;this->t = t;int flow = 0;while (BFS()) {                  // 每次BFS構建層次網絡memset(cur, 0, sizeof(cur)); // 重置當前弧flow += DFS(s, inf);         // 進行多路增廣，累加流量}return flow;}// 返回最小割的邊集合（需在Maxflow之后調用）vector<int> Mincut() {vector<int> ans;for (int i = 0; i < edges.size(); i++) {edge &e = edges[i];// 若邊的起點在層次網絡中可達，終點不可達，且為原始正向邊if (vis[e.from] && !vis[e.to] && e.cap > 0)ans.push_back(i);}return ans;}
} dinic;signed main() {cin.tie(0)->ios::sync_with_stdio(0);int n, m, s, t;cin >> n >> m >> s >> t;dinic.init(n + 5); // 初始化Dinic結構體while (m--) {int s, t, u;cin >> s >> t >> u;dinic.addedge(s, t, u); // 添加邊}// 計算從節點s到節點t的最大流cout << dinic.Maxflow(s, t);return 0;
}

2. ISAP算法（Improved Shortest Augmenting Path）

? 原理：

動態分層：初始BFS分層后，逆向維護層次值（從匯點開始更新）。
重貼標簽：當某層節點耗盡時，調整節點層次（類似最大流中的GAP優化）。
單次BFS：僅需一次BFS初始化，后續通過回溯調整層次，減少重復分層。
? 時間復雜度： $O(n^2 m)$ ，常數優于Dinic，適合大規模稀疏圖。
? 適用問題：最大流問題，尤其適合邊數較多的圖。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <ctime>
using namespace std;
const int maxn = 1100;
const int maxedges = 51000;
const int inf = 1 << 30;
struct edge {int to, flow;edge *next, *pair;edge() {}edge(int to, int flow, edge *next) : to(to), flow(flow), next(next) {}void *operator new(unsigned, void *p) { return p; }
};
struct ISAP {int gap[maxn], h[maxn], n, s, t;edge *cur[maxn], *first[maxn], edges[maxedges * 2], *ptr;void init(int n) {this->n = n;ptr = edges;memset(first, 0, sizeof(first));memset(gap, 0, sizeof(gap));memset(h, 0, sizeof(h));gap[0] = n;}void add_edge(int from, int to, int cap) {first[from] = new(ptr++)edge(to, cap, first[from]);first[to] = new(ptr++)edge(from, 0, first[to]);first[from]->pair = first[to];first[to]->pair = first[from];}int augment(int x, int limit) {if (x == t)return limit;int rest = limit;for (edge*& e = cur[x]; e; e = e->next) if (e->flow && h[e->to] + 1 == h[x]) {int d = augment(e->to, min(rest, e->flow));e->flow -= d, e->pair->flow += d, rest -= d;if (h[s] == n || !rest)return limit - rest;}int minh = n;for (edge *e = cur[x] = first[x]; e; e = e->next) if (e->flow)minh = min(minh, h[e->to] + 1);if (--gap[h[x]] == 0)h[s] = n;else++gap[h[x] = minh];return limit - rest;}int solve(int s, int t, int limit = inf) {this->s = s; this->t = t;memcpy(cur, first, sizeof(first)); // memcpy!int flow = 0;while (h[s] < n && flow < limit)flow += augment(s, limit - flow);return flow;}
}isap;
int main()
{freopen("D:\\in.txt", "r", stdin);int n, m;scanf("%d %d", &n, &m);isap.init(n + 5);while (m--){int s, t, u;scanf("%d %d %d", &s, &t, &u);isap.add_edge(s, t, u);}auto start = clock();printf("%d\n", isap.solve(1, n));double tot = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;printf("Isap: %f\n", tot);return 0;
}

3. HLPP算法（Highest Label Preflow Push）

? 原理：

預流推進：允許節點暫時超額流量，通過“推進”操作將流量推向匯點。
最高標號優先：優先處理層次高的活躍節點，用優先隊列維護。
GAP優化：當層次出現斷層時，直接標記斷層上方節點為不可達。
? 時間復雜度： $(O(n^2 \sqrt{m}))$ ，理論最優，適合超大規模數據。
? 適用問題：最大流問題，在特定題目中比Dinic/ISAP快數倍。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <ctime>
using namespace std;
const int maxn = 2e5 + 5, maxedges = 4e6 + 5, inf = 0x3f3f3f3f;
int n, m, s, t, tot;
int v[maxedges * 2], w[maxedges * 2], first[maxn], nxt[maxedges * 2];
int h[maxn], e[maxn], gap[maxn * 2], inq[maxn];//節點高度是可以到達2n-1的
struct cmp{inline bool operator()(int a, int b) const {return h[a] < h[b];//因為在優先隊列中的節點高度不會改變，所以可以直接比較}
};
queue<int> Q;
priority_queue<int, vector<int>, cmp> heap;
inline void add_edge(int from, int to, int flow) {tot += 2;v[tot + 1] = from; v[tot] = to; w[tot] = flow; w[tot + 1] = 0;nxt[tot] = first[from]; first[from] = tot;nxt[tot + 1] = first[to]; first[to] = tot + 1;return;
}
inline bool bfs() {memset(h + 1, 0x3f, sizeof(int) * n);h[t] = 0; Q.push(t);while (!Q.empty()){int now = Q.front(); Q.pop();for (int go = first[now]; go; go = nxt[go])if (w[go ^ 1] && h[v[go]] > h[now] + 1)h[v[go]] = h[now] + 1, Q.push(v[go]);}return h[s] != inf;
}
inline void push(int now) {for (int go = first[now]; go; go = nxt[go]) {if (w[go] && h[v[go]] + 1 == h[now]) {int d = min(e[now], w[go]);w[go] -= d; w[go ^ 1] += d; e[now] -= d; e[v[go]] += d;if (v[go] != s && v[go] != t && !inq[v[go]])heap.push(v[go]), inq[v[go]] = 1;if (!e[now])//已經推送完畢可以直接退出break;}}
}
inline void relabel(int now) {h[now] = inf;for (int go = first[now]; go; go = nxt[go])if (w[go] && h[v[go]] + 1 < h[now])h[now] = h[v[go]] + 1;return;
}
inline int hlpp() {int now, d;if (!bfs()) //s和t不連通return 0;h[s] = n;memset(gap, 0, sizeof(int) * (n * 2));for (int i = 1; i <= n; i++)if (h[i] < inf)++gap[h[i]];for (int go = first[s]; go; go = nxt[go]) {if (d = w[go]) {w[go] -= d; w[go ^ 1] += d; e[s] -= d; e[v[go]] += d;if (v[go] != s && v[go] != t && !inq[v[go]])heap.push(v[go]), inq[v[go]] = 1;}}while (!heap.empty()) {inq[now = heap.top()] = 0; heap.pop(); push(now);if (e[now]) {if (!--gap[h[now]]) //gap優化，因為當前節點是最高的所以修改的節點一定不在優先隊列中，不必擔心修改對優先隊列會造成影響for (int i = 1; i <= n; i++)if (i != s && i != t && h[i] > h[now] && h[i] < n + 1)h[i] = n + 1;relabel(now); ++gap[h[now]];heap.push(now); inq[now] = 1;}}return e[t];
}
int main()
{freopen("D:\\in.txt", "r", stdin);scanf("%d %d", &n, &m); s = 1; t = n;while (m--){int s, t, u;scanf("%d %d %d", &s, &t, &u);add_edge(s, t, u);}auto start = clock();printf("%d\n", hlpp());double tot = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;printf("HLPP: %f\n", tot);return 0;
}

4. MCMF-SPFA

? 原理：

SPFA找最短路：每次用SPFA（隊列優化的Bellman-Ford）找費用最小的增廣路。
沿最短路增廣：在最短路徑上調整流量并更新殘余網絡。
? 特點：
? 支持負權邊，但SPFA可能被卡到 $O (nm)$ 。
? 適合費用流中存在負權但邊數較少的圖。
? 適用問題：最小費用最大流問題（費用流）。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;
const int maxn = 20100;
const int inf = 1 << 30;
struct edge {int from, to, cap, flow, cost;edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w) {}
};
struct MCMF {int n, m;vector<edge> edges;vector<int> G[maxn];int inq[maxn];int d[maxn];int p[maxn];int a[maxn];void init(int n) {this->n = n;for (int i = 0; i < n; ++i)G[i].clear();edges.clear();}void add_edge(int from, int to, int cap, int cost) {edges.push_back(edge(from, to, cap, 0, cost));edges.push_back(edge(to, from, 0, 0, -cost));m = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}bool BellmanFord(int s, int t, int &flow, int &cost, int limit) {for (int i = 0; i < n; ++i)d[i] = inf;memset(inq, 0, sizeof(inq));d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = inf;queue<int> Q;Q.push(s);while (!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = false;for (unsigned i = 0; i < G[u].size(); ++i) {edge &e = edges[G[u][i]];if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {d[e.to] = d[u] + e.cost;p[e.to] = G[u][i];a[e.to] = min(a[u], e.cap - e.flow);if (!inq[e.to]) {Q.push(e.to);inq[e.to] = true;}}}}if (d[t] == inf)return false;a[t] = min(a[t], limit - flow);flow += a[t];cost += d[t] * a[t];for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}return true;}int solve(int s, int t, int limit = inf) {int flow = 0, cost = 0;while (flow < limit && BellmanFord(s, t, flow, cost, limit));return cost;}
}mcmf;
int main()
{freopen("D:\\in.txt", "r", stdin);int n, m, k;scanf("%d %d %d", &n, &m, &k);mcmf.init(n + 10);for (int i = 1; i <= m; ++i) {int x, y, c, w;scanf("%d %d %d %d", &x, &y, &c, &w);mcmf.add_edge(x, y, c, w);}auto start = clock();printf("%d\n", mcmf.solve(1, n, k));double tot = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;printf("MCMF-spfa: %f\n", tot);return 0;
}

5. MCMF-Dijkstra

? 原理：

勢函數去負權：通過勢函數 $h (u)$ 調整邊權，使得所有邊權非負。
Dijkstra找最短路：用Dijkstra代替SPFA，時間復雜度更穩定。
勢函數更新：每次增廣后更新勢函數，保持邊權非負。
? 時間復雜度： $\log n)$ ， $f$ 為最大流量，適合正權圖。
? 適用問題：最小費用最大流問題，且圖中無負權或通過勢函數消除負權。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;
const int maxn = 21000;
const int inf = 1 << 30;
struct edge {int to, cap, cost, rev;edge() {}edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {}
};
struct MCMF {int n, h[maxn], d[maxn], pre[maxn], num[maxn];vector<edge> G[maxn];void init(int n) {this->n = n;for (int i = 0; i <= n; ++i)G[i].clear();}void add_edge(int from, int to, int cap, int cost) {G[from].push_back(edge(to, cap, cost, G[to].size()));G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));}//flow是自己傳進去的變量，就是最后的最大流，返回的是最小費用int solve(int s, int t, int &flow, int limit = inf) {int cost = 0; memset(h, 0, sizeof(h));while (limit) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > Q;for (int i = 0; i <= n; ++i)d[i] = inf;d[s] = 0; Q.emplace(0, s);while (!Q.empty()) {auto now = Q.top(); Q.pop();int u = now.second;if (d[u] < now.first) continue;for (int i = 0; i < G[u].size(); ++i) {edge &e = G[u][i];if (e.cap > 0 && d[e.to] > d[u] + e.cost + h[u] - h[e.to]) {d[e.to] = d[u] + e.cost + h[u] - h[e.to];pre[e.to] = u;num[e.to] = i;Q.emplace(d[e.to], e.to);}}}if (d[t] == inf) break;for (int i = 0; i <= n; ++i)h[i] += d[i];int a = limit;for (int u = t; u != s; u = pre[u])a = min(a, G[pre[u]][num[u]].cap);limit -= a; flow += a; cost += a * h[t];for (int u = t; u != s; u = pre[u]) {edge &e = G[pre[u]][num[u]];e.cap -= a;G[u][e.rev].cap += a;}}return cost;}
}mcmf;
int main()
{freopen("D:\\in.txt", "r", stdin);int n, m, k, flow = 0;scanf("%d %d %d", &n, &m, &k);mcmf.init(n + 10);for (int i = 1; i <= m; ++i) {int x, y, c, w;scanf("%d %d %d %d", &x, &y, &c, &w);mcmf.add_edge(x, y, c, w);}auto start = clock();printf("%d\n", mcmf.solve(1, n, flow, k));printf("flow: %d\n", flow);double tot = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;printf("MCMF-dijkstra: %f\n", tot);return 0;
}

（代碼來自孫明志大佬的xcpc算法模板）

總結

? 最大流問題：優先選擇Dinic或ISAP（代碼簡單），超大規模數據用HLPP。
? 費用流問題：
? 含負權邊 → MCMF-SPFA。
? 無負權邊 → MCMF-Dijkstra（更高效）。
? 關鍵區別：
? Dinic/ISAP/HLPP解決最大流，MCMF類解決費用流。
? SPFA允許負權但慢，Dijkstra需正權但快；HLPP通過預流推進優化最大流。