網絡流（進階）

最大流：DINIC or SAP

最小費用最大流：SPFA+增廣(費用的值較離散) or ZKW(費用的值集中)

有源彙的上下界最大流：建立s', t',用(i, j, l, r)表示i到j有一條下界為l上界為r的邊，将每條這樣的邊拆成(s', j, 0, l), (i, t', 0, l), (i, j, 0, r-l)，加入邊(t, s, 0, max)再從s‘到t'求最大流，再去掉(t, s, 0, max)這條邊，從s到t求最大流

有源彙的上下界最小可行流：基本同上，将最後一步改成從t到s反求一遍最大流來退流；也可以二分(t, s, 0, max)這條邊的容量

有源彙的上下界最小費用可行流：拆邊方法同上，從s'向t'求一遍最小費用最大流

有源彙的上下界最小費用最大流：基本同上，還要再s向t求一遍最小費用最大流(*這個是自己YY的，可能不對，求指教)

無源彙的最大流(無向圖全局最小割)：Stoer-Wagner算法

無源彙的所有點對間最大流：分治，在目前點集内随便選兩個點求最小割，用這個割更新一遍所有跨在兩邊的點對(不一定隻是目前點集内的點)，再将自己的點集割成兩部分，遞歸做

無源彙的上下界可行流：拆邊，直接從s'到t'跑一遍最大流

無源彙的上下界最小費用可行流：拆邊，直接從s'到t'跑一遍最小費用最大流

平面圖最小割轉最短路：将平面區域當成點，兩個點之間的邊權為原來這兩個平面區域之間的邊的容量，補上一條彙到源的正無窮邊之後，求這條正無窮邊的一邊到另一邊的最短路

有上下界的網絡流問題：點選打開連結

====================================================================================================================================

變形很多，最小割最大流定理的了解是關鍵

POJ 1149 - PIGS(較難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1149

絕對經典的構圖題

POJ 1273 - Drainage Ditches(基礎)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

最大流入門

POJ 1459 - Power Network(基礎)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1459

基本構圖

POJ 1637 - Sightseeing tour(Crazy)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1637

題意：求混合圖的歐拉迹是否存在

解法：無向邊任意定向，構圖，詳建黑書P324

POJ 1815 - Friendship(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1815

題意：求最小點割

解法：拆點轉換為邊割

相關：http://hi.baidu.com/zfy0701/blog/item/a521f230b06dea9fa9018e0e.html

POJ 1966 - Cable TV Network(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1966

題意：去掉多少點讓圖不連通

解法：任定一源點，枚舉彙點求點割集(轉換到求邊割)，求其中最小的點割

POJ 2112 - Optimal Milking(基礎)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2112

二分枚舉，最大流

POJ 2391 - Ombrophobic Bovines(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2391

題意：floyd, 拆點，二分枚舉

相關：http://hi.baidu.com/zfy0701/blog/item/3e0006c4f73f0eaf8226acff.html

POJ 2396 - Budget(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2396

題意：有源彙的上下界可行流

解法：用矩陣-網絡流模型構圖，然後拆邊

相關：http://hi.baidu.com/zfy0701/blog/item/6449d82a64e15e3e5343c1ba.html

最小割模型在競賽中的應用

POJ 2455 - Secret Milking Machine(基礎)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2455

二分枚舉，一般來說需要寫對邊容量的更新操作而不是每次全部重新構圖

POJ 2699 - The Maximum Number of Strong Kings(較難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2699

解法：枚舉人數 + 最大流(感謝xpcnq_71大牛的建圖的提示)

POJ 2987 - Firing(較難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2987

題意：最大權閉包

解法：先邊權放大，第一問總量-最大流，第二問求最小割

相關：http://wywcgs.spaces.live.com/blog/cns!4D861A02A3382142!1109.entry?&_c02_owner=1

Profit(中等)

http://www.vijos.cn/Problem_Show.asp?id=1352

最大權閉包圖的特殊情況

ZOJ 2071 - Technology Trader 也是此類型，懶了沒做

http://acm.zju.edu.cn/show_problem.php?pid=2071

POJ 3084 - Panic Room(中等，好題)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3084

題意：略

解法：根據最小割模組化

POJ 3155 - Hard Life(很挑戰一題)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3155

題意：最大密度子圖

解法：參數搜尋 + 最大權閉合圖，A.V.Goldberg的論文(nb解法)

最小割模型在資訊學競賽中的應用 一文中也有講

POJ 3189 - Steady Cow Assignment(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3189

題意：尋找最小的區間完成比對

解法：這題充分說明SAP的強大，純暴力可過。更好的方法是在枚舉區間的過程中不斷删邊和加邊繼續網絡流過程

POJ 3204 - Ikki's Story I - Road Reconstruction(基礎)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3204

ZOJ 2532 - Internship(基礎)

http://acm.zju.edu.cn/show_problem.php?pid=2532

題意：确定邊是否是某個割中的邊

解法：兩邊dfs求割, 或暴力枚舉(需要寫取消某條增廣路的操作(但資料弱，也許不取消也能混過))

POJ 3308 - Paratroopers(較難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3308

POJ 2125 - Destroying The Graph(難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2125

題意：最小點權覆寫

POJ 3469 - Dual Core CPU(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3469

題意：最小割

POJ 3498 - March of the Penguins(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3498

題意：滿足點容量限制的網絡流

解法：拆點把點容量轉換為邊容量，枚舉彙點

ZOJ 2587 - Unique Attack(較難)

http://acm.zju.edu.cn/show_problem.php?pid=2587

題意：确定最小割是否是唯一的

解法：得了解dfs求最小割算法的本質

SPOJ 839 - Optimal Marks(難)

http://www.spoj.pl/problems/OPTM/

解法：很經典哦，見amber的集訓隊論文，根據标号的每一位求最小割

SGU 326 - Perspective(中等)

http://acm.sgu.ru/problem.php?c0&problem=326

比較經典的構圖法

費用流問題

可以KM解的就不放在這裡，另外，感覺除非很特殊的圖，一般用連續增廣路的算法就夠了

POJ 2175 - Evacuation Plan(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2175

題意：判斷是否給定解是最優解，比較陰的一題

解法：根據給出的計劃構造流，然後消且隻消一次負圈

POJ 3422 - Kaka's Matrix Travels(中等)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3422

解法：拆點

POJ 3680 - Intervals(較難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3680

題意：略，這題還是蠻經典

解法：discuss中比較詳細

SPOJ 371 - Boxes(簡單)

http://www.spoj.pl/problems/BOXES/

解法：費用流，但似乎有比網絡流更好的做法

SGU 185 - Two shortest(中等)

http://acm.sgu.ru/problem.php?c0&problem=185

題意：求兩條不想交的最短路徑