如果說最大流是“如何用最快的速度把水從A送到B”那么最小割就是“如何用最少的代價(jià)切斷A到B的所有通路”——它用一張網(wǎng)絡(luò)和一把“剪刀”回答了所有阻斷問題的最優(yōu)解。引言假設(shè)你是一名指揮官敵軍有一條從后方基地到前線的補(bǔ)給線網(wǎng)絡(luò)——多條道路交織四通八達(dá)。你的任務(wù)是炸掉最少的道路或者說花費(fèi)最小的代價(jià)讓補(bǔ)給徹底無法送達(dá)前線。每條道路的炸毀成本不同你該怎么選這個(gè)問題在算法競(jìng)賽中有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)模型——最小割Minimum Cut。而“最大流等于最小割”這條定理則是解決這類問題的核心武器。你第一天接手三鹿牛奶公司就發(fā)生了一件倒霉的事情公司不小心發(fā)送了一批有三聚氰胺的牛奶。送貨網(wǎng)很大關(guān)系復(fù)雜壞牛奶已經(jīng)進(jìn)入了這個(gè)網(wǎng)絡(luò)。你的任務(wù)是在保證壞牛奶不送到零售商節(jié)點(diǎn)N的前提下停止某些運(yùn)輸卡車使損失最小——同時(shí)在損失最小的前提下還要讓停止的卡車數(shù)量最少。這就是洛谷 P1344 [USACO4.4] 追查壞牛奶 Pollutant Control要解決的問題?！叭绻f網(wǎng)絡(luò)流是圖論中的‘水利工程’那么最小割就是它的‘定向爆破’——你不需要關(guān)心水怎么流只需要知道在哪里切斷最劃算。”前置知識(shí)在閱讀本文之前建議你熟悉以下概念流網(wǎng)絡(luò)Flow Network一個(gè)有向圖每條邊有容量capacity源點(diǎn)source產(chǎn)生流量匯點(diǎn)sink接收流量。最大流Maximum Flow從源點(diǎn)到匯點(diǎn)能輸送的最大流量。增廣路Augmenting Path在殘留網(wǎng)絡(luò)中從源點(diǎn)到匯點(diǎn)的一條路徑沿它可以增加流量。DFS與BFSDinic算法的基礎(chǔ)遍歷手段。時(shí)間復(fù)雜度分析理解算法的漸近復(fù)雜度。第一章從“割”說起——最小割是什么1.1 割的定義把圖一分為二在一個(gè)流網(wǎng)絡(luò)中一個(gè)割Cut就是把所有節(jié)點(diǎn)分成兩個(gè)集合——SS和TT滿足源點(diǎn)s∈S匯點(diǎn)t∈T。割的容量Capacity定義為所有從S指向T的邊的容量之和。換句話說割的容量就是你為了切斷s到t的所有通路需要“剪掉”的那些邊的總?cè)萘俊?.2 最小割最便宜的“斷交”方案最小割Minimum Cut就是在所有可能的割中容量最小的那個(gè)割。為什么最小割重要因?yàn)樗卮鹆艘粋€(gè)核心問題切斷源點(diǎn)到匯點(diǎn)的所有路徑最少需要付出多少代價(jià)這正好對(duì)應(yīng)了P1344的第一問——“使壞牛奶無法送達(dá)零售商的最小經(jīng)濟(jì)損失”。1.3 一個(gè)生活中的類比想象一個(gè)供水網(wǎng)絡(luò)自來水廠源點(diǎn)向你家匯點(diǎn)供水中間經(jīng)過無數(shù)管道和水閘。現(xiàn)在政府要檢修管道需要關(guān)閉一些水閘讓你家暫時(shí)停水。每個(gè)水閘的關(guān)閉成本不同——有的閘門銹了很難關(guān)成本高有的很好關(guān)成本低。最小割就是告訴你關(guān)哪些水閘既能讓水完全停掉又花最少的錢。這就是最小割的直覺——花最少的代價(jià)徹底阻斷。第二章最大流最小割定理——解決問題的“核武器”2.1 定理的直觀理解最大流最小割定理Max-Flow Min-Cut Theorem是網(wǎng)絡(luò)流理論中最核心的定理之一在一個(gè)流網(wǎng)絡(luò)中從源點(diǎn)到匯點(diǎn)的最大流量等于最小割的容量。這個(gè)定理為什么成立直觀上可以這樣理解最大流不可能大于最小割因?yàn)樗袕膕到t的流量都必須經(jīng)過任意一個(gè)割而割的容量限制了能通過的總流量。最大流不可能小于最小割如果最大流小于某個(gè)割的容量說明網(wǎng)絡(luò)還沒有被充分利用可以繼續(xù)增廣。所以兩者必然相等。2.2 定理的證明思路簡要嚴(yán)格的證明通常分兩步任意流 ≤ 任意割的容量對(duì)于任意可行流f和任意割(S,T)流的值等于從S流出的凈流量不可能超過割的容量。存在一個(gè)流達(dá)到最小割的容量當(dāng)算法如Ford-Fulkerson終止時(shí)殘留網(wǎng)絡(luò)中不存在增廣路。此時(shí)定義S為從源點(diǎn)能到達(dá)的所有節(jié)點(diǎn)T為其余節(jié)點(diǎn)則(S,T)是一個(gè)割且其容量恰好等于當(dāng)前流的值。因此最大流 最小割。2.3 這個(gè)定理給我們的“便利”這個(gè)定理最大的實(shí)用價(jià)值在于求最小割等價(jià)于求最大流。也就是說我們不需要單獨(dú)設(shè)計(jì)一個(gè)“求最小割”的算法——只需要跑一遍最大流比如Dinic算法得到的最大流數(shù)值就是最小割的容量。在P1344中第一問“最小的經(jīng)濟(jì)損失”就是直接跑最大流的結(jié)果。第三章P1344的挑戰(zhàn)——不僅要最小還要最少3.1 題目的兩個(gè)要求P1344要求輸出兩個(gè)整數(shù)C最小的損失即最小割的容量T在損失最小的前提下最少要停止的卡車數(shù)即最小割中包含的邊數(shù)第一問很簡單——直接建圖跑最大流。難點(diǎn)在第二問最小割可能有多種方案我們要從中選出邊數(shù)最少的那一個(gè)。也就是說在“最小損失”和“最少停運(yùn)卡車數(shù)”之間前者優(yōu)先級(jí)更高。3.2 樸素思路的問題一個(gè)直觀的想法是先跑一遍最大流求出最小割的容量然后把所有邊的容量改成1再跑一遍最大流得到最少邊數(shù)。這樣做確實(shí)可行但要跑兩遍網(wǎng)絡(luò)流代碼量大、常數(shù)也大。在算法競(jìng)賽中我們追求更優(yōu)雅的一次建圖、一次跑流的解法。3.3 核心技巧邊權(quán)編碼既然要同時(shí)優(yōu)化兩個(gè)目標(biāo)——主目標(biāo)損失最小優(yōu)先級(jí)高于輔目標(biāo)邊數(shù)最少——我們可以把兩個(gè)目標(biāo)“編碼”到同一條邊的容量中。具體做法是將每條邊的容量從 w 改為 w×K1其中 KK 是一個(gè)大于總邊數(shù) MM 的數(shù)。為什么這樣做設(shè)一個(gè)割包含 kk 條邊其容量為∑(wi×K1)K×∑wik第一部分 K×∑wi反映的是經(jīng)濟(jì)損失主目標(biāo)第二部分 k 反映的是割邊數(shù)量輔目標(biāo)因?yàn)?KM≥k所以任何兩個(gè)割的比較首先看的是 ∑wi 的大小主目標(biāo)優(yōu)先只有當(dāng) ∑wi 相等時(shí)才會(huì)比較 k 的大小輔目標(biāo)。3.4 K 應(yīng)該取多大題目中 M≤1000所以 K 取1001或更大的數(shù)即可。如果 K1001那么任何兩個(gè)最小割方案只要損失差 ≥1編碼后的容量差就至少是 1001遠(yuǎn)超邊數(shù)差的最大值 1000主目標(biāo)一定優(yōu)先。跑完最大流后ans / K就是最小損失 Cans % K就是最少邊數(shù) T。3.5 為什么是 1 而不是 0如果只乘 K 而不加 1那么所有割的編碼容量都是 K 的倍數(shù)邊數(shù)信息就丟失了。1的作用就是把邊數(shù)編碼進(jìn)余數(shù)部分——每條被割的邊貢獻(xiàn) 1總邊數(shù)就是余數(shù)。第四章經(jīng)典例題精解——洛谷 P1344 追查壞牛奶4.1 題目呈現(xiàn)題目來源洛谷 P1344 [USACO4.4] 追查壞牛奶 Pollutant Control題目描述你第一天接手三鹿牛奶公司就發(fā)生了一件倒霉的事情公司不小心發(fā)送了一批有三聚氰胺的牛奶。送貨網(wǎng)由一些倉庫和運(yùn)輸卡車組成每輛卡車都在各自固定的兩個(gè)倉庫之間單向運(yùn)輸牛奶。你的任務(wù)是在保證壞牛奶不送到零售商倉庫 N的前提下停止某些運(yùn)輸卡車使損失最小。輸入格式第一行兩個(gè)整數(shù) N(2≤N≤32)、M(0≤M≤1000)第 22 到 M1 行每行三個(gè)整數(shù) Si,Ei,Ci表示從 Si到 Ei 的一條有向邊容量停止損失為 Ci輸出格式兩個(gè)整數(shù) C 和 TC 表示最小的損失T表示在損失最小的前提下最少要停止的卡車數(shù)輸入樣例4 5 1 3 100 3 2 50 2 4 60 1 2 40 2 3 80輸出樣例60 14.2 建模分析把每個(gè)倉庫看作節(jié)點(diǎn)每輛卡車看作一條有向邊邊的容量就是停止這輛卡車的經(jīng)濟(jì)損失。源點(diǎn) s1發(fā)貨工廠匯點(diǎn) tN零售商目標(biāo)是讓 1 和 N 不連通即找到一個(gè)割。最小割的容量就是最小的經(jīng)濟(jì)損失。4.3 核心代碼C17#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 35; // N 32 const int MAXM 1005; // M 1000 const ll INF 4e18; const ll K 1001; // 大于 M 的大數(shù) struct Edge { int to, rev; ll cap; }; vectorEdge g[MAXN]; int level[MAXN], iter[MAXN]; int n, m; // 添加一條有向邊及其反向邊 void add_edge(int from, int to, ll cap) { g[from].push_back({to, (int)g[to].size(), cap}); g[to].push_back({from, (int)g[from].size() - 1, 0}); } // BFS 構(gòu)建層次圖 bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int v q.front(); q.pop(); for (auto e : g[v]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[v] 1; q.push(e.to); } } } return level[t] 0; } // DFS 尋找增廣路 ll dfs(int v, int t, ll f) { if (v t) return f; for (int i iter[v]; i (int)g[v].size(); i) { Edge e g[v][i]; if (e.cap 0 level[v] level[e.to]) { ll d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; g[e.to][e.rev].cap d; return d; } } } return 0; } // Dinic 最大流 ll max_flow(int s, int t) { ll flow 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); ll f; while ((f dfs(s, t, INF)) 0) { flow f; } } return flow; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 0; i m; i) { int u, v; ll w; cin u v w; // 核心技巧邊權(quán)編碼為 w * K 1 add_edge(u, v, w * K 1); } ll ans max_flow(1, n); cout ans / K ans % K \n; return 0; }4.4 代碼詳解第34-36行添加邊時(shí)容量設(shè)置為w * K 1。這就是核心的編碼技巧。第38-60行標(biāo)準(zhǔn)Dinic算法。bfs構(gòu)建層次圖dfs在層次圖上尋找增廣路。第67-68行跑完最大流后ans / K得到最小損失主目標(biāo)ans % K得到最少邊數(shù)輔目標(biāo)4.5 樣例驗(yàn)證輸入樣例中M5M5K1001K1001。各邊編碼后的容量1-3100×100111001013-250×10011500512-460×10011600611-240×10011400412-380×1001180081跑最大流得到 ans60061割掉邊2-4容量60邊數(shù)1。C60061/100160T60061%10011輸出60 1與樣例一致。4.6 復(fù)雜度分析時(shí)間復(fù)雜度Dinic算法在一般圖上的復(fù)雜度為 O(V^2E)。本題 V≤32E≤1000完全可行?？臻g復(fù)雜度O(VE)。4.7 另一種思路兩遍最大流除了編碼技巧也可以分兩次建圖第一遍按原邊權(quán)建圖跑最大流得到最小損失 C。第二遍將所有邊的容量改為1跑最大流得到最少邊數(shù) T。這種方法更直觀但需要跑兩遍代碼量略大。編碼技巧則一次建圖、一次跑流更加簡潔高效?？偨Y(jié)網(wǎng)絡(luò)流最小割是算法競(jìng)賽中一個(gè)極其重要的模型。從“切斷補(bǔ)給線”到“追查壞牛奶”它的核心思想始終如一用最小的代價(jià)徹底阻斷源點(diǎn)到匯點(diǎn)的所有通路。而最大流最小割定理則為我們提供了一個(gè)強(qiáng)大的工具——求最小割就是求最大流。P1344這道題的精髓在于多目標(biāo)優(yōu)化的處理技巧當(dāng)我們需要在“主目標(biāo)最優(yōu)”的前提下優(yōu)化“輔目標(biāo)”時(shí)可以通過邊權(quán)編碼的方式把兩個(gè)目標(biāo)合并到一條邊的容量中一次最大流同時(shí)解決兩個(gè)問題。三個(gè)關(guān)鍵點(diǎn)核心定理最大流 最小割求最小割就是求最大流。核心技巧邊權(quán)編碼為 w×K1KM一次最大流同時(shí)得到最小割值和最少邊數(shù)。核心模型凡是“切斷所有通路的最小代價(jià)”類問題都可以建模為最小割。“最小割教會(huì)我們有時(shí)候解決問題的最佳方式不是找到最快的路而是找到最便宜的‘?dāng)嗦贰袛嘤袝r(shí)比連通更需要智慧。”參考文獻(xiàn)與延伸閱讀《算法導(dǎo)論》Introduction to Algorithms第26章——最大流OI-Wiki網(wǎng)絡(luò)流 - 最小割洛谷 P1344 [USACO4.4] 追查壞牛奶 Pollutant Control《最小割模型在信息學(xué)競(jìng)賽中的應(yīng)用》—— 胡伯濤國家集訓(xùn)隊(duì)論文HDU 6214 Smallest Minimum Cut—— 同類練習(xí)題