如果說最大流是“如何用最快的速度把水從A送到B”那么最小割就是“如何用最少的代價切斷A到B的所有通路”——它用一張網絡和一把“剪刀”回答了所有阻斷問題的最優解。引言假設你是一名指揮官敵軍有一條從后方基地到前線的補給線網絡——多條道路交織四通八達。你的任務是炸掉最少的道路或者說花費最小的代價讓補給徹底無法送達前線。每條道路的炸毀成本不同你該怎么選這個問題在算法競賽中有一個標準的數學模型——最小割Minimum Cut。而“最大流等于最小割”這條定理則是解決這類問題的核心武器。你第一天接手三鹿牛奶公司就發生了一件倒霉的事情公司不小心發送了一批有三聚氰胺的牛奶。送貨網很大關系復雜壞牛奶已經進入了這個網絡。你的任務是在保證壞牛奶不送到零售商節點N的前提下停止某些運輸卡車使損失最小——同時在損失最小的前提下還要讓停止的卡車數量最少。這就是洛谷 P1344 [USACO4.4] 追查壞牛奶 Pollutant Control要解決的問題。“如果說網絡流是圖論中的‘水利工程’那么最小割就是它的‘定向爆破’——你不需要關心水怎么流只需要知道在哪里切斷最劃算。”前置知識在閱讀本文之前建議你熟悉以下概念流網絡Flow Network一個有向圖每條邊有容量capacity源點source產生流量匯點sink接收流量。最大流Maximum Flow從源點到匯點能輸送的最大流量。增廣路Augmenting Path在殘留網絡中從源點到匯點的一條路徑沿它可以增加流量。DFS與BFSDinic算法的基礎遍歷手段。時間復雜度分析理解算法的漸近復雜度。第一章從“割”說起——最小割是什么1.1 割的定義把圖一分為二在一個流網絡中一個割Cut就是把所有節點分成兩個集合——SS和TT滿足源點s∈S匯點t∈T。割的容量Capacity定義為所有從S指向T的邊的容量之和。換句話說割的容量就是你為了切斷s到t的所有通路需要“剪掉”的那些邊的總容量。1.2 最小割最便宜的“斷交”方案最小割Minimum Cut就是在所有可能的割中容量最小的那個割。為什么最小割重要因為它回答了一個核心問題切斷源點到匯點的所有路徑最少需要付出多少代價這正好對應了P1344的第一問——“使壞牛奶無法送達零售商的最小經濟損失”。1.3 一個生活中的類比想象一個供水網絡自來水廠源點向你家匯點供水中間經過無數管道和水閘。現在政府要檢修管道需要關閉一些水閘讓你家暫時停水。每個水閘的關閉成本不同——有的閘門銹了很難關成本高有的很好關成本低。最小割就是告訴你關哪些水閘既能讓水完全停掉又花最少的錢。這就是最小割的直覺——花最少的代價徹底阻斷。第二章最大流最小割定理——解決問題的“核武器”2.1 定理的直觀理解最大流最小割定理Max-Flow Min-Cut Theorem是網絡流理論中最核心的定理之一在一個流網絡中從源點到匯點的最大流量等于最小割的容量。這個定理為什么成立直觀上可以這樣理解最大流不可能大于最小割因為所有從s到t的流量都必須經過任意一個割而割的容量限制了能通過的總流量。最大流不可能小于最小割如果最大流小于某個割的容量說明網絡還沒有被充分利用可以繼續增廣。所以兩者必然相等。2.2 定理的證明思路簡要嚴格的證明通常分兩步任意流 ≤ 任意割的容量對于任意可行流f和任意割(S,T)流的值等于從S流出的凈流量不可能超過割的容量。存在一個流達到最小割的容量當算法如Ford-Fulkerson終止時殘留網絡中不存在增廣路。此時定義S為從源點能到達的所有節點T為其余節點則(S,T)是一個割且其容量恰好等于當前流的值。因此最大流 最小割。2.3 這個定理給我們的“便利”這個定理最大的實用價值在于求最小割等價于求最大流。也就是說我們不需要單獨設計一個“求最小割”的算法——只需要跑一遍最大流比如Dinic算法得到的最大流數值就是最小割的容量。在P1344中第一問“最小的經濟損失”就是直接跑最大流的結果。第三章P1344的挑戰——不僅要最小還要最少3.1 題目的兩個要求P1344要求輸出兩個整數C最小的損失即最小割的容量T在損失最小的前提下最少要停止的卡車數即最小割中包含的邊數第一問很簡單——直接建圖跑最大流。難點在第二問最小割可能有多種方案我們要從中選出邊數最少的那一個。也就是說在“最小損失”和“最少停運卡車數”之間前者優先級更高。3.2 樸素思路的問題一個直觀的想法是先跑一遍最大流求出最小割的容量然后把所有邊的容量改成1再跑一遍最大流得到最少邊數。這樣做確實可行但要跑兩遍網絡流代碼量大、常數也大。在算法競賽中我們追求更優雅的一次建圖、一次跑流的解法。3.3 核心技巧邊權編碼既然要同時優化兩個目標——主目標損失最小優先級高于輔目標邊數最少——我們可以把兩個目標“編碼”到同一條邊的容量中。具體做法是將每條邊的容量從 w 改為 w×K1其中 KK 是一個大于總邊數 MM 的數。為什么這樣做設一個割包含 kk 條邊其容量為∑(wi×K1)K×∑wik第一部分 K×∑wi反映的是經濟損失主目標第二部分 k 反映的是割邊數量輔目標因為 KM≥k所以任何兩個割的比較首先看的是 ∑wi 的大小主目標優先只有當 ∑wi 相等時才會比較 k 的大小輔目標。3.4 K 應該取多大題目中 M≤1000所以 K 取1001或更大的數即可。如果 K1001那么任何兩個最小割方案只要損失差 ≥1編碼后的容量差就至少是 1001遠超邊數差的最大值 1000主目標一定優先。跑完最大流后ans / K就是最小損失 Cans % K就是最少邊數 T。3.5 為什么是 1 而不是 0如果只乘 K 而不加 1那么所有割的編碼容量都是 K 的倍數邊數信息就丟失了。1的作用就是把邊數編碼進余數部分——每條被割的邊貢獻 1總邊數就是余數。第四章經典例題精解——洛谷 P1344 追查壞牛奶4.1 題目呈現題目來源洛谷 P1344 [USACO4.4] 追查壞牛奶 Pollutant Control題目描述你第一天接手三鹿牛奶公司就發生了一件倒霉的事情公司不小心發送了一批有三聚氰胺的牛奶。送貨網由一些倉庫和運輸卡車組成每輛卡車都在各自固定的兩個倉庫之間單向運輸牛奶。你的任務是在保證壞牛奶不送到零售商倉庫 N的前提下停止某些運輸卡車使損失最小。輸入格式第一行兩個整數 N(2≤N≤32)、M(0≤M≤1000)第 22 到 M1 行每行三個整數 Si,Ei,Ci表示從 Si到 Ei 的一條有向邊容量停止損失為 Ci輸出格式兩個整數 C 和 TC 表示最小的損失T表示在損失最小的前提下最少要停止的卡車數輸入樣例4 5 1 3 100 3 2 50 2 4 60 1 2 40 2 3 80輸出樣例60 14.2 建模分析把每個倉庫看作節點每輛卡車看作一條有向邊邊的容量就是停止這輛卡車的經濟損失。源點 s1發貨工廠匯點 tN零售商目標是讓 1 和 N 不連通即找到一個割。最小割的容量就是最小的經濟損失。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 的大數 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 構建層次圖 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; // 核心技巧邊權編碼為 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行添加邊時容量設置為w * K 1。這就是核心的編碼技巧。第38-60行標準Dinic算法。bfs構建層次圖dfs在層次圖上尋找增廣路。第67-68行跑完最大流后ans / K得到最小損失主目標ans % K得到最少邊數輔目標4.5 樣例驗證輸入樣例中M5M5K1001K1001。各邊編碼后的容量1-3100×100111001013-250×10011500512-460×10011600611-240×10011400412-380×1001180081跑最大流得到 ans60061割掉邊2-4容量60邊數1。C60061/100160T60061%10011輸出60 1與樣例一致。4.6 復雜度分析時間復雜度Dinic算法在一般圖上的復雜度為 O(V^2E)。本題 V≤32E≤1000完全可行。空間復雜度O(VE)。4.7 另一種思路兩遍最大流除了編碼技巧也可以分兩次建圖第一遍按原邊權建圖跑最大流得到最小損失 C。第二遍將所有邊的容量改為1跑最大流得到最少邊數 T。這種方法更直觀但需要跑兩遍代碼量略大。編碼技巧則一次建圖、一次跑流更加簡潔高效。總結網絡流最小割是算法競賽中一個極其重要的模型。從“切斷補給線”到“追查壞牛奶”它的核心思想始終如一用最小的代價徹底阻斷源點到匯點的所有通路。而最大流最小割定理則為我們提供了一個強大的工具——求最小割就是求最大流。P1344這道題的精髓在于多目標優化的處理技巧當我們需要在“主目標最優”的前提下優化“輔目標”時可以通過邊權編碼的方式把兩個目標合并到一條邊的容量中一次最大流同時解決兩個問題。三個關鍵點核心定理最大流 最小割求最小割就是求最大流。核心技巧邊權編碼為 w×K1KM一次最大流同時得到最小割值和最少邊數。核心模型凡是“切斷所有通路的最小代價”類問題都可以建模為最小割。“最小割教會我們有時候解決問題的最佳方式不是找到最快的路而是找到最便宜的‘斷路’——切斷有時比連通更需要智慧。”參考文獻與延伸閱讀《算法導論》Introduction to Algorithms第26章——最大流OI-Wiki網絡流 - 最小割洛谷 P1344 [USACO4.4] 追查壞牛奶 Pollutant Control《最小割模型在信息學競賽中的應用》—— 胡伯濤國家集訓隊論文HDU 6214 Smallest Minimum Cut—— 同類練習題