1、(2010-02-07 18:00:40)標簽：分類：ACM雜談最大流POJ 1459 Power NetworkUVa 563 CrimewaveUVa 820 Internet Bandwidth枚舉+構圖ZOJ 2332 GemsHOJ 2634 How to earn morePOJ 3308 ParatroopersHDU 1569方格取數(shù)(2)(最大點權獨立集)將異或操作轉化為對每一位求最小割HOJ 2811 Earthquake Damage （最小點割集）2008 Beijing Regional Contest Problem A Destroying the bus sta

2、tions （ BFS 預處理）（IZOJ 3241 Being a Hero有上下界原匯最小最小費用流HOJ 2715 Matrix3HOJ 2739 The Chinese Postman ProblemPOJ 2175 Evacuation Plan （消一次負圈）POJ 3422 Kaka,s Matrix Travels （與 Matrix3 類似）POJ 2516 Minimum Cost （按物品種類多次建圖）POJ 2195 Going HomeBUAA 1032 Destroying a Painting出所有最小權IPOJ 3680 IntervalsHOJ 2543 St

3、one IVPOJ 2135 Farm TourBASHU2445餐巾問題onmylove 原創(chuàng)最大流題目：TC：Single Round Match 399 Round 1 - Division I, Level Three同 Hoj1024:混合圖的歐拉回路Poj1637:求增廣邊：Poj3204:類似:Hoj1082: &pid=6pku圖論、網(wǎng)絡流入門題總結、匯總（2009-10-07 23:25:25）轉載標簽： 分類：acm 圖論題雜談POJ 2449 Remmarguts Date（中等）題意：經(jīng)典問題：K短路解法：dijkstra+A*（rec），方法很多相關：該題亦放在搜索推

4、薦題中POJ 3013 - Big Christmas Tree（基礎）題意：最簡單最短路，但此題要過，需要較好的程序速度和，還要注意精度解法：DijkstraPOJ 3463 - Sightseeing（中等）題意：最短路和比最短路大1的路的數(shù)量解法：需要真正理解dijkstraPOJ 3613 - Cow Relays（較難）題意：求經(jīng)過N條邊的最短路解法：floyd +倍增，貪心POJ 3621 - Sightseeing Cows（中等）題意：求一個環(huán)路，歡樂值/總路徑最大解法：參數(shù)搜索+最短路（ms原始的bellman tle,用spfa才過）POJ 3635 - full tank

5、?（中等）題意：最短路變形解法：廣搜相關：生成樹問題基本的生成樹就不放上來了POJ 1639 - Picnic Planning（較難）題意：頂點度數(shù)有限制的最小生成樹解法：貪心 + prim/kruskalPOJ 1679 - The Unique MST（基礎）題意：判斷MST是否唯一解法：prim就行，不過還是易錯的題POJ 2728 - Desert King（中等）題意：所謂最優(yōu)比率生成樹解法：參數(shù)搜索 + primPOJ 3164 - Command Network（難）題意：最小樹形圖解法：劉朱算法，這個考到的可能性比較小吧?POJ 3522 - Slim Span（基礎）題意：

6、求一顆生成樹，讓最大邊最小邊差值最小解法：kruskal活用連通性，度數(shù)，拓撲問題此類問題主要牽扯到DFS，縮點等技巧POJ 1236 - Network of Schools（基礎）題意：問添加多少邊可成為完全連通圖解法：縮點，看度數(shù)POJ 1659 - Frogs Neighborhood（基礎）題意：根據(jù)度序列構造圖解法：貪心，詳細證明參見havel定理POJ 2553 - The Bottom of a Graph（基礎）POJ 2186 - Popular Cows（基礎）題意：強連通分量縮點圖出度為0的點POJ 2762 - Going from u to v or from v

7、to u?（中等）題意：單向連通圖判定解法：縮點+ dp找最長鏈POJ 2914 - Minimum Cut（難）題意：無向圖最小割解法：Stoer-Wagner算法，用網(wǎng)絡流加枚舉判定會掛POJ 2942 - Knights of the Round Table（難）題意：求雙聯(lián)通分量（或稱塊）中是否含奇圈解法：求出雙連通分量后做黑白染色進行二分圖圖判定相關：3177 - Redundant Paths（中等）POJ 3352 - Road Construction（中等）題意：添加多少條邊可成為雙向連通圖解法：把割邊分開的不同分量縮點構樹，看入度建議對比下1236，有向圖添加多少條邊變成強

8、連通圖POJ 3249 - Test for Job（基礎）解法：bfs / dfs + dpPOJ 3592 - Instantaneous Transference（基礎）解法：縮點，最長路，少人做的水題，注意細節(jié)POJ 3687 - Labeling Balls（中等）解法：拓撲排序POJ 3694 - Network（中等）解法：雙連通分量+并查集2-SAT問題此類問題理解合取式的含義就不難POJ 2723 - Get Luffy Out（中等）POJ 2749 - Building roads（較難）解法：二分+ 2-SAT判定POJ 3207 - Ikkis Story IV -

9、Pandas Trick（基 礎）解法：簡單的2-sat，不過其他方法更快POJ 3648- Wedding（中等）解法：用2-sat做會比較有意思，但是暴搜照樣0msPOJ 3678 - Katu Puzzle（基礎）解法：直接按合取式構圖驗證就行了POJ 3683 - Priest Johns Busiest Day（中等）解法：n2枚舉點之間的相容性構圖，求解2-SAT最大流問題變形很多，最小割最大流定理的理解是關鍵POJ 1149 - PIGS（較難）絕對經(jīng)典的構圖題最大流入門POJ 1459 - Power Network（基礎）基本構圖POJ 1637 - Sightseeing

10、tour（Crazy）題意：求混合圖的歐拉跡是否存在解法：無向邊任意定向，構圖，詳建黑書P324POJ 1815 - Friendship（中等）題意：求最小點割解法：拆點轉換為邊割相關：1966 - Cable TV Network（中等）題意：去掉多少點讓圖不連通解法：任定一源點，枚舉匯點求點割集（轉換到求邊割），求其中最小的點割POJ 2112 - Optimal Milking（基礎）二分枚舉，最大流POJ 2391 - Ombrophobic Bovines（中等）題意：floyd,拆點，二分枚舉相關：2396 - Budget（中等）題意：有源匯的上下界可行流解法：用矩陣-網(wǎng)絡流模

11、型構圖，然后拆邊相關：，最小割模型在競賽中的應用POJ 2455 - Secret Milking Machine（基礎）二分枚舉，一般來說需要寫對邊容量的更新操作而不是每次全部重新構圖POJ 2699 - The Maximum Number of Strong Kings（較難）解法：枚舉人數(shù)+最大流（感謝xpcnq_71大牛的建圖的提示）POJ 2987 - Firing（較難）題意：最大權閉包解法：先邊權放大，第一問總量-最大流，第二問求最小割相關：&_c02_owner=1Profit（中等）最大權閉包圖的特殊情況ZOJ 2071 - Technology Trader 也是此類型，

12、懶了沒做3084 - Panic Room（中等，好題）題意：略解法：根據(jù)最小割建模POJ 3155 - Hard Life（很 挑戰(zhàn)一題）題意：最大密度子圖解法：參數(shù)搜索+最大權閉合圖，的論文（nb解法）最小割模型在信息學競賽中的應用一文中也有講POJ 3189 - Steady Cow Assignment（中等）題意：尋找最小的區(qū)間完成匹配解法：這題充分說明SAP的強大，純暴力可過。更好的方法是在枚舉區(qū)間的過程中不斷刪邊 和加邊繼續(xù)網(wǎng)絡流過程POJ 3204 - Ikkis Story I - Road Reconstruction（基 礎）ZOJ 2532 - Internship（基

13、礎）題意：確定邊是否是某個割中的邊解法：兩邊dfs求割，或暴力枚舉（需要寫取消某條增廣路的操作（但數(shù)據(jù)弱，也許不取消也 能混過）POJ 3308 - Paratroopers（較難）POJ 2125 - Destroying The Graph（難）題意：最小點權覆蓋POJ 3469 - Dual Core CPU（中等）題意：最小割POJ 3498 - March of the Penguins（中等）題意：滿足點容量限制的網(wǎng)絡流解法：拆點把點容量轉換為邊容量，枚舉匯點ZOJ 2587 - Unique Attack（較難）題意：確定最小割是否是唯一的解法：得理解dfs求最小割算法的本質SP

14、OJ 839 - Optimal Marks（難）題意：略解法：很經(jīng)典哦，見amber的集訓隊論文，根據(jù)標號的每一位求最小割SGU 326 - Perspective（中等）&problem=326比較經(jīng)典的構圖法費用流問題可以KM解的就不放在這里，另外，感覺除非很特殊的圖，一般用連續(xù)增廣路的算法就夠了POJ 2175 - Evacuation Plan（中等）題意：判斷是否給定解是最優(yōu)解，比較陰的一題解法：根據(jù)給出的計劃構造流，然后消且只消一次負圈POJ 3422 - Kakas Matrix Travels（中等）題意：略解法：拆點POJ 3680 - Intervals（較難）題意：略，

15、這題還是蠻經(jīng)典解法：discuss中比較詳細SPOJ 371 - Boxes（簡單）題意：略解法：費用流，但似乎有比網(wǎng)絡流更好的做法SGU 185 - Two shortest（中等）&problem=185題意：求兩條不想交的最短路徑解法：費用流，也可以最短路+最大流。匹配問題正確理解KM算法是很重要的這里我還要說幾句：最正確解最小權匹配的辦法是用一個很大的數(shù)-當前邊權值，而不是直接對邊權取反（這樣只能處理左右點相等的完全二分圖，即K（n, n）以上有可能還是說的有點問題，以后補充POJ 1486 - Sorting Slides（中等）題意：二分圖的必須邊解法：需正真理解最大匹配算法，詳見

16、1904 - Kings Quest（中等，好題）題意：求二分圖所有可能的匹配邊解法：雖然最終不是用匹配算法，但需要理解匹配的思想轉換成強連通分量問題。POJ 2060 -Taxi Cab Scheme（基礎）題意：最小路徑覆蓋POJ 2594 -Treasure Exploration（中等）題意：可相交最小路徑覆蓋解法：先傳遞閉包轉化下POJ 3041 - Asteroids（基礎）POJ 2226 - Muddy Fields（基礎）題意：行列的覆蓋解法：最小點集覆蓋=最大匹配POJ 2195 - Going Home（基 礎）題意：最小權值匹配解法：KM算法POJ 2400 - Sup

17、ervisor, Supervisee（中等）題意：輸出所有最小權匹配解法：KM,然后回溯解，汗，輸入的兩個矩陣居然是反過來的POJ 2516 -Minimum Cost（中等）題意：最小權值匹配或最小費用流解法：拆點+ KM算法（只有正確的才能過），費用流（ms錯的可能也能過）POJ 3686 - The Windys（較難）題意：最小權值匹配解法：拆點，然后盡管用KM算法去水吧，數(shù)據(jù)其實弱得不得了 O（50 * 50 * 2500） - 16ms相關：412 - K-path cover（較難）題意：略解法：很牛叉的一道匹配相關：206. Roads（較難）&problem=206解法：經(jīng)典題目，也可以使用spoj 412那題的優(yōu)化NP問題一般是搜索或dp解的POJ 1419 - Graph Coloring（基礎）題意：圖的著色解法：搜索，可惜題目的數(shù)據(jù)真是太弱了POJ 2989 - All Friends（難）題意：極大團數(shù)量解法：開始狂 tle,后來找了論文：Finding All Cliques of an Undirected Graph（CoenBron & Joep Kerboscht）ZOJ 1492 - Maximum Clique（基礎）題意：圖的最大團解法：搜索，如果要求速度，可參考下相應論文其他不能成大類的POJ 1470 - Closest C