網(wǎng)絡(luò)流題目集錦.doc

網(wǎng)絡(luò)流題目集錦（轉(zhuǎn)）(2010-02-07 18:00:40) 轉(zhuǎn)載標(biāo)簽： 雜談分類：ACM最大流POJ 1273 Drainage DitchesPOJ 1274 The Perfect Stall (二分圖匹配)POJ 1698 Alices ChancePOJ 1459 Power NetworkPOJ 2112 Optimal Milking (二分)POJ 2455 Secret Milking Machine (二分)POJ 3189 Steady Cow Assignment (枚舉)POJ 1637 Sightseeing tour (混合圖歐拉回路)POJ 3498 March of the Penguins (枚舉匯點(diǎn))POJ 1087 A Plug for UNIXPOJ 1149 Pigs (構(gòu)圖題)ZOJ 2760 How Many Shortest Path (邊不相交最短路的條數(shù))POJ 2391 Ombrophobic Bovines (必須拆點(diǎn)，否則有BUG)WHU 1124 Football Coach (構(gòu)圖題)SGU 326 Perspective (構(gòu)圖題，類似于 WHU 1124)UVa 563 CrimewaveUVa 820 Internet BandwidthPOJ 3281 Dining (構(gòu)圖題)POJ 3436 ACM Computer FactoryPOJ 2289 Jamies Contact Groups (二分)SGU 438 The Glorious Karlutka River =) (按時(shí)間拆點(diǎn))SGU 242 Students Morning (輸出一組解)SGU 185 Two shortest (Dijkstra 預(yù)處理，兩次增廣，必須用鄰接陣實(shí)現(xiàn)，否則 MLE)HOJ 2816 Power LinePOJ 2699 The Maximum Number of Strong Kings (枚舉+構(gòu)圖)ZOJ 2332 GemsJOJ 2453 Candy (構(gòu)圖題)SOJ3312 Stockholm KnightsSOJ3353 Total FlowSOJ2414 Leapin Lizards 最小割SOJ3106 Dual Core CPUSOJ3109 Space flightSOJ3107 SelectSOJ3185 Black and whiteSOJ3254 Rain and FgjSOJ3134 windy和水星 - 水星交通HOJ 2634 How to earn moreZOJ 2071 Technology Trader (找割邊)HNU 10940 CoconutsZOJ 2532 Internship (找關(guān)鍵割邊)POJ 1815 Friendship (字典序最小的點(diǎn)割集)POJ 3204 Ikkis Story I - Road Reconstruction (找關(guān)鍵割邊)POJ 3308 ParatroopersPOJ 3084 Panic RoomPOJ 3469 Dual Core CPUZOJ 2587 Unique Attack (最小割的唯一性判定)POJ 2125 Destroying The Graph (找割邊)ZOJ 2539 Energy MinimizationTJU 2944 Mussy Paper (最大權(quán)閉合子圖)POJ 1966 Cable TV Network (無向圖點(diǎn)連通度)HDU 1565 方格取數(shù)(1) (最大點(diǎn)權(quán)獨(dú)立集)HDU 1569 方格取數(shù)(2) (最大點(diǎn)權(quán)獨(dú)立集)POJ 2987 Firing (最大權(quán)閉合子圖)SPOJ 839 Optimal Marks (將異或操作轉(zhuǎn)化為對(duì)每一位求最小割)HOJ 2811 Earthquake Damage (最小點(diǎn)割集)2008 Beijing Regional Contest Problem A Destroying the bus stations ( BFS 預(yù)處理 )(http:/acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4322)ZOJ 2676 Network Wars (參數(shù)搜索)POJ 3155 Hard Life (參數(shù)搜索)ZOJ 3241 Being a Hero有上下界ZOJ 2314 Reactor Cooling (無源匯可行流)POJ 2396 Budget (有源匯可行流)SGU 176 Flow Construction (有源匯最小流)ZOJ 3229 Shoot the Bullet (有源匯最大流)HDU 3157 Crazy Circuits (有源匯最小流)最小費(fèi)用流HOJ 2715 Matrix3HOJ 2739 The Chinese Postman ProblemPOJ 2175 Evacuation Plan (消一次負(fù)圈)POJ 3422 Kakas Matrix Travels (與 Matrix3 類似)POJ 2516 Minimum Cost (按物品種類多次建圖)POJ 2195 Going HomeBUAA 1032 Destroying a PaintingPOJ 2400 Supervisor, Supervisee (輸出所有最小權(quán)匹配)POJ 3680 IntervalsHOJ 2543 Stone IVPOJ 2135 Farm TourBASHU2445 餐巾問題-onmylove原創(chuàng)最大流題目：TC：Single Round Match 200 Round 1 Division I, Level ThreeSingle Round Match 236 Round 1 Division I, Level ThreeSingle Round Match 399 Round 1 Division I, Level Three同Hoj1024: /thx/problem.php?id=10242003 TCO Semifinal Round 4 Division I, Level Three2004 TCCC Championship Round Division I, Level Three2005 TCO Sponsor Track Round 3 Division I, Level One混合圖的歐拉回路Poj1637: /JudgeOnline/problem?id=1637zju1992：/show_problem.php?pid=1992 求增廣邊：Poj3204：/JudgeOnline/problem?id=3204類似：Hoj1082: /thx/problem.php?cid=1017&pid=6pku圖論、網(wǎng)絡(luò)流入門題總結(jié)、匯總(2009-10-07 23:25:25) 轉(zhuǎn)載標(biāo)簽： 雜談分類：acm_圖論題POJ 2449 Remmarguts Date(中等)/JudgeOnline/problem?id=2449題意：經(jīng)典問題：K短路解法：dijkstra+A*(rec)，方法很多相關(guān)：/JudgeOnline/showcontest?contest_id=1144該題亦放在搜索推薦題中POJ 3013 - Big Christmas Tree(基礎(chǔ))/JudgeOnline/problem?id=3013題意：最簡單最短路，但此題要過，需要較好的程序速度和，還要注意精度解法：DijkstraPOJ 3463 - Sightseeing(中等)/JudgeOnline/problem?id=3463題意：最短路和比最短路大1的路的數(shù)量解法：需要真正理解dijkstraPOJ 3613 - Cow Relays(較難)/JudgeOnline/problem?id=3613題意：求經(jīng)過N條邊的最短路解法：floyd + 倍增，貪心POJ 3621 - Sightseeing Cows(中等)/JudgeOnline/problem?id=3621題意：求一個(gè)環(huán)路，歡樂值 / 總路徑最大解法：參數(shù)搜索 + 最短路(ms 原始的bellman tle, 用spfa才過)POJ 3635 - full tank?(中等)/JudgeOnline/problem?id=3635題意：最短路變形解法：廣搜相關(guān)：/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html生成樹問題基本的生成樹就不放上來了POJ 1639 - Picnic Planning(較難)/JudgeOnline/problem?id=1639題意：頂點(diǎn)度數(shù)有限制的最小生成樹解法：貪心 + prim/kruskalPOJ 1679 - The Unique MST(基礎(chǔ))/JudgeOnline/problem?id=1679題意：判斷MST是否唯一解法：prim就行，不過還是易錯(cuò)的題POJ 2728 - Desert King(中等)/JudgeOnline/problem?id=2728題意：所謂最優(yōu)比率生成樹解法：參數(shù)搜索 + primPOJ 3164 - Command Network(難)/JudgeOnline/problem?id=3164題意：最小樹形圖解法：劉朱算法，這個(gè)考到的可能性比較小吧？POJ 3522 - Slim Span(基礎(chǔ))/JudgeOnline/problem?id=3522題意：求一顆生成樹，讓最大邊最小邊差值最小解法：kruskal活用連通性，度數(shù)，拓?fù)鋯栴}此類問題主要牽扯到DFS，縮點(diǎn)等技巧POJ 1236 - Network of Schools(基礎(chǔ))/JudgeOnline/problem?id=1236題意：問添加多少邊可成為完全連通圖解法：縮點(diǎn)，看度數(shù)POJ 1659 - Frogs Neighborhood(基礎(chǔ))/JudgeOnline/problem?id=1659題意：根據(jù)度序列構(gòu)造圖解法：貪心，詳細(xì)證明參見havel定理POJ 2553 - The Bottom of a Graph(基礎(chǔ))/JudgeOnline/problem?id=2553POJ 2186 - Popular Cows(基礎(chǔ))/JudgeOnline/problem?id=2186題意：強(qiáng)連通分量縮點(diǎn)圖出度為0的點(diǎn)POJ 2762 - Going from u to v or from v to u?(中等)/JudgeOnline/problem?id=2762題意：單向連通圖判定解法：縮點(diǎn) + dp找最長鏈POJ 2914 - Minimum Cut(難)/JudgeOnline/problem?id=2914題意：無向圖最小割解法：Stoer-Wagner算法，用網(wǎng)絡(luò)流加枚舉判定會(huì)掛POJ 2942 - Knights of the Round Table(難)/JudgeOnline/problem?id=2942題意：求雙聯(lián)通分量(或稱塊)中是否含奇圈解法：求出雙連通分量后做黑白染色進(jìn)行二分圖圖判定相關(guān)：/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.htmlPOJ 3177 - Redundant Paths(中等)/JudgeOnline/problem?id=3177POJ 3352 - Road Construction(中等)/JudgeOnline/problem?id=3352題意：添加多少條邊可成為雙向連通圖解法：把割邊分開的不同分量縮點(diǎn)構(gòu)樹，看入度建議對(duì)比下1236，有向圖添加多少條邊變成強(qiáng)連通圖POJ 3249 - Test for Job(基礎(chǔ))/JudgeOnline/problem?id=3249解法：bfs / dfs + dpPOJ 3592 - Instantaneous Transference(基礎(chǔ))/JudgeOnline/problem?id=3592解法：縮點(diǎn)，最長路，少人做的水題，注意細(xì)節(jié)POJ 3687 - Labeling Balls(中等)/JudgeOnline/problem?id=3687解法：拓?fù)渑判騊OJ 3694 - Network(中等)/JudgeOnline/problem?id=3694解法：雙連通分量+并查集2-SAT問題此類問題理解合取式的含義就不難POJ 2723 - Get Luffy Out(中等)/JudgeOnline/problem?id=2723POJ 2749 - Building roads(較難)/JudgeOnline/problem?id=2749解法：二分 + 2-SAT判定POJ 3207 - Ikkis Story IV - Pandas Trick(基礎(chǔ))/JudgeOnline/problem?id=3207解法：簡單的2-sat，不過其他方法更快POJ 3648- Wedding(中等)/JudgeOnline/problem?id=3648解法：用2-sat做會(huì)比較有意思，但是暴搜照樣0msPOJ 3678 - Katu Puzzle(基礎(chǔ))/JudgeOnline/problem?id=3678解法：直接按合取式構(gòu)圖驗(yàn)證就行了POJ 3683 - Priest Johns Busiest Day(中等)/JudgeOnline/problem?id=3683解法：n2枚舉點(diǎn)之間的相容性構(gòu)圖，求解2-SAT最大流問題變形很多，最小割最大流定理的理解是關(guān)鍵POJ 1149 - PIGS(較難)/JudgeOnline/problem?id=1149絕對(duì)經(jīng)典的構(gòu)圖題POJ 1273 - Drainage Ditches(基礎(chǔ))/JudgeOnline/problem?id=1273最大流入門POJ 1459 - Power Network(基礎(chǔ))/JudgeOnline/problem?id=1459基本構(gòu)圖POJ 1637 - Sightseeing tour(Crazy)/JudgeOnline/problem?id=1637題意：求混合圖的歐拉跡是否存在解法：無向邊任意定向，構(gòu)圖，詳建黑書P324POJ 1815 - Friendship(中等)/JudgeOnline/problem?id=1815題意：求最小點(diǎn)割解法：拆點(diǎn)轉(zhuǎn)換為邊割相關(guān)：/zfy0701/blog/item/a521f230b06dea9fa9018e0e.htmlPOJ 1966 - Cable TV Network(中等)/JudgeOnline/problem?id=1966題意：去掉多少點(diǎn)讓圖不連通解法：任定一源點(diǎn)，枚舉匯點(diǎn)求點(diǎn)割集(轉(zhuǎn)換到求邊割)，求其中最小的點(diǎn)割POJ 2112 - Optimal Milking(基礎(chǔ))/JudgeOnline/problem?id=2112二分枚舉，最大流POJ 2391 - Ombrophobic Bovines(中等)/JudgeOnline/problem?id=2391題意：floyd, 拆點(diǎn)，二分枚舉相關(guān)：/zfy0701/blog/item/3e0006c4f73f0eaf8226acff.htmlPOJ 2396 - Budget(中等)/JudgeOnline/problem?id=2396題意：有源匯的上下界可行流解法：用矩陣-網(wǎng)絡(luò)流模型構(gòu)圖，然后拆邊相關(guān)：/zfy0701/blog/item/6449d82a64e15e3e5343c1ba.html，最小割模型在競賽中的應(yīng)用POJ 2455 - Secret Milking Machine(基礎(chǔ))/JudgeOnline/problem?id=2455二分枚舉，一般來說需要寫對(duì)邊容量的更新操作而不是每次全部重新構(gòu)圖POJ 2699 - The Maximum Number of Strong Kings(較難)/JudgeOnline/problem?id=2699解法：枚舉人數(shù) + 最大流(感謝xpcnq_71大牛的建圖的提示)POJ 2987 - Firing(較難)/JudgeOnline/problem?id=2987題意：最大權(quán)閉包解法：先邊權(quán)放大，第一問總量-最大流，第二問求最小割相關(guān)：/blog/cns!4D861A02A3382142!1109.entry?&_c02_owner=1Profit(中等)/Problem_Show.asp?id=1352最大權(quán)閉包圖的特殊情況ZOJ 2071 - Technology Trader 也是此類型，懶了沒做/show_problem.php?pid=2071POJ 3084 - Panic Room(中等，好題)/JudgeOnline/problem?id=3084題意：略解法：根據(jù)最小割建模POJ 3155 - Hard Life(很挑戰(zhàn)一題)/JudgeOnline/problem?id=3155題意：最大密度子圖解法：參數(shù)搜索 + 最大權(quán)閉合圖，A.V.Goldberg的論文(nb解法)最小割模型在信息學(xué)競賽中的應(yīng)用 一文中也有講POJ 3189 - Steady Cow Assignment(中等)/JudgeOnline/problem?id=3189題意：尋找最小的區(qū)間完成匹配解法：這題充分說明SAP的強(qiáng)大，純暴力可過。更好的方法是在枚舉區(qū)間的過程中不斷刪邊和加邊繼續(xù)網(wǎng)絡(luò)流過程POJ 3204 - Ikkis Story I - Road Reconstruction(基礎(chǔ))/JudgeOnline/problem?id=3204ZOJ 2532 - Internship(基礎(chǔ))/show_problem.php?pid=2532題意：確定邊是否是某個(gè)割中的邊解法：兩邊dfs求割, 或暴力枚舉(需要寫取消某條增廣路的操作(但數(shù)據(jù)弱，也許不取消也能混過)POJ 3308 - Paratroopers(較難)/JudgeOnline/problem?id=3308POJ 2125 - Destroying The Graph(難)/JudgeOnline/problem?id=2125題意：最小點(diǎn)權(quán)覆蓋POJ 3469 - Dual Core CPU(中等)/JudgeOnline/problem?id=3469題意：最小割POJ 3498 - March of the Penguins(中等)/JudgeOnline/problem?id=3498題意：滿足點(diǎn)容量限制的網(wǎng)絡(luò)流解法：拆點(diǎn)把點(diǎn)容量轉(zhuǎn)換為邊容量，枚舉匯點(diǎn)ZOJ 2587 - Unique Attack(較難)/show_problem.php?pid=2587題意：確定最小割是否是唯一的解法：得理解dfs求最小割算法的本質(zhì)SPOJ 839 - Optimal Marks(難)http:/www.spoj.pl/problems/OPTM/題意：略解法：很經(jīng)典哦，見amber的集訓(xùn)隊(duì)論文，根據(jù)標(biāo)號(hào)的每一位求最小割SGU 326 - Perspective(中等)http:/acm.sgu.ru/problem.php?c0&problem=326比較經(jīng)典的構(gòu)圖法費(fèi)用流問題可以KM解的就不放在這里，另外，感覺除非很特殊的圖，一般用連續(xù)增廣路的算法就夠了POJ 2175 - Evacuation Plan(中等)/JudgeOnline/problem?id=2175題意：判斷是否給定解是最優(yōu)解，比較陰的一題解法：根據(jù)給出的計(jì)劃構(gòu)造流，然后消且只消一次負(fù)圈POJ 3422 - Kakas Matrix Travels(中等)/JudgeOnline/problem?id=3422題意：略解法：拆點(diǎn)POJ 3680 - Intervals(較難)/JudgeOnline/problem?id=3680題意：略，這題還是蠻經(jīng)典解法：discuss中比較詳細(xì)SPOJ 371 - Boxes(簡單)http:/www.spoj.pl/problems/BOXES/題意：略解法：費(fèi)用流，但似乎有比網(wǎng)絡(luò)流更好的做法SGU 185 - Two shortest(中等)http:/acm.sgu.ru/problem.php?c0&problem=185題意：求兩條不想交的最短路徑解法：費(fèi)用流，也可以最短路 + 最大流。匹配問題正確理解KM算法是很重要的這里我還要說幾句：最正確解最小權(quán)匹配的辦法是用一個(gè)很大的數(shù)-當(dāng)前邊權(quán)值，而不是直接對(duì)邊權(quán)取反(這樣只能處理左右點(diǎn)相等的完全二分圖，即K(n, n)以上有可能還是說的有點(diǎn)問題，以后補(bǔ)充POJ 1486 - Sorting Slides(中等)/JudgeOnline/problem?id=1486題意：二分圖的必須邊解法：需正真理解最大匹配算法，詳見/kevin0602/blog/item/1d5be63b5bec9bec14cecb44.htmlPOJ 1904 - Kings Quest(中等，好題)/JudgeOnline/problem?id=1904題意：求二分圖所有可能的匹配邊解法：雖然最終不是用匹配算法，但需要理解匹配的思想轉(zhuǎn)換成強(qiáng)連通分量問題。POJ 2060 -Taxi Cab Scheme(基礎(chǔ))/JudgeOnline/problem?id=2060題意：最小路徑覆蓋POJ 2594 -Treasure Exploration(中等)/JudgeOnline/problem?id=2594題意：可相交最小路徑覆蓋解法：先傳遞閉包轉(zhuǎn)化下POJ 3041 - Asteroids(基礎(chǔ))/JudgeOnline/problem?id=3041POJ 2226 - Muddy Fields(基礎(chǔ))/JudgeOnline/problem?id=2226題意：行列的覆蓋解法：最小點(diǎn)集覆蓋 = 最大匹配POJ 2195 - Going Home(基礎(chǔ))/JudgeOnline/problem?id=2195題意：最小權(quán)值匹配解法：KM算法POJ 2400 - Supervisor, Supervisee(中等)/JudgeOnline/problem?id=2400題意：輸出所有最小權(quán)匹配解法：KM, 然后回溯解，汗，輸入的兩個(gè)矩陣居然是反過來的POJ 2516 -Minimum Cost(中等)/JudgeOnline/problem?id=2516題意：最小權(quán)值匹配或最小費(fèi)用流解法：拆點(diǎn) + KM算法(只有正確的才能過)，費(fèi)用流(ms錯(cuò)的可能也能過)POJ 3686 - The Windys(較難)/JudgeOnline/problem?id=3686題意：最小權(quán)值匹配解法：拆點(diǎn),然后盡管用KM算法去水吧，數(shù)據(jù)其實(shí)弱得不得了 O(50 * 50 * 2500) - 16ms相關(guān)：/kevin0602/blog/item/2829d