POJ 2449 Remmarguts' Date(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
題意：經(jīng)典問(wèn)題：K短路
解法：dijkstra+A*(rec)，方法很多
相關(guān)：http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144
該題亦放在搜索推薦題中

POJ 3013 - Big Christmas Tree(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3013
題意：最簡(jiǎn)單最短路，但此題要過(guò)，需要較好的程序速度和，還要注意精度
解法：Dijkstra

POJ 3463 - Sightseeing(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3463
題意：最短路和比最短路大1的路的數(shù)量
解法：需要真正理解dijkstra

POJ 3613 - Cow Relays(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3613
題意：求經(jīng)過(guò)N條邊的最短路
解法：floyd + 倍增，貪心

POJ 3621 - Sightseeing Cows(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3621
題意：求一個(gè)環(huán)路，歡樂(lè)值 / 總路徑最大
解法：參數(shù)搜索 + 最短路(ms 原始的bellman tle, 用spfa才過(guò))

POJ 3635 - full tank?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3635
題意：最短路變形
解法：廣搜
相關(guān)：http://hi.baidu.com/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html

生成樹(shù)問(wèn)題
基本的生成樹(shù)就不放上來(lái)了

POJ 1639 - Picnic Planning(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1639
題意：頂點(diǎn)度數(shù)有限制的最小生成樹(shù)
解法：貪心 + prim/kruskal

POJ 1679 - The Unique MST(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1679
題意：判斷MST是否唯一
解法：prim就行，不過(guò)還是易錯(cuò)的題

POJ 2728 - Desert King(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2728
題意：所謂最優(yōu)比率生成樹(shù)
解法：參數(shù)搜索 + prim

POJ 3164 - Command Network(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3164
題意：最小樹(shù)形圖
解法：劉朱算法，這個(gè)考到的可能性比較小吧？

POJ 3522 - Slim Span(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3522
題意：求一顆生成樹(shù)，讓最大邊最小邊差值最小
解法：kruskal活用

連通性，度數(shù)，拓?fù)鋯?wèn)題
此類問(wèn)題主要牽扯到DFS，縮點(diǎn)等技巧

POJ 1236 - Network of Schools(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1236
題意：?jiǎn)柼砑佣嗌龠吙沙蔀橥耆B通圖
解法：縮點(diǎn)，看度數(shù)

POJ 1659 - Frogs' Neighborhood(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1659
題意：根據(jù)度序列構(gòu)造圖
解法：貪心，詳細(xì)證明參見(jiàn)havel定理

POJ 2553 - The Bottom of a Graph(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2553
POJ 2186 - Popular Cows(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2186
題意：強(qiáng)連通分量縮點(diǎn)圖出度為0的點(diǎn)

POJ 2762 - Going from u to v or from v to u?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2762
題意：?jiǎn)蜗蜻B通圖判定
解法：縮點(diǎn) + dp找最長(zhǎng)鏈

POJ 2914 - Minimum Cut(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2914
題意：無(wú)向圖最小割
解法：Stoer-Wagner算法，用網(wǎng)絡(luò)流加枚舉判定會(huì)掛

POJ 2942 - Knights of the Round Table(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2942
題意：求雙聯(lián)通分量(或稱塊)中是否含奇圈
解法：求出雙連通分量后做黑白染色進(jìn)行二分圖圖判定
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.html

POJ 3177 - Redundant Paths(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3177
POJ 3352 - Road Construction(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3352
題意：添加多少條邊可成為雙向連通圖
解法：把割邊分開(kāi)的不同分量縮點(diǎn)構(gòu)樹(shù)，看入度
建議對(duì)比下1236，有向圖添加多少條邊變成強(qiáng)連通圖

POJ 3249 - Test for Job(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3249
解法：bfs / dfs + dp

POJ 3592 - Instantaneous Transference(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3592
解法：縮點(diǎn)，最長(zhǎng)路，少人做的水題，注意細(xì)節(jié)

POJ 3687 - Labeling Balls(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3687
解法：拓?fù)渑判?/p>

POJ 3694 - Network(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3694
解法：雙連通分量+并查集

2-SAT問(wèn)題
此類問(wèn)題理解合取式的含義就不難

POJ 2723 - Get Luffy Out(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2723
POJ 2749 - Building roads(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2749
解法：二分 + 2-SAT判定

POJ 3207 - Ikki's Story IV - Panda's Trick(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3207
解法：簡(jiǎn)單的2-sat，不過(guò)其他方法更快

POJ 3648- Wedding(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3648
解法：用2-sat做會(huì)比較有意思，但是暴搜照樣0ms

POJ 3678 - Katu Puzzle(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3678
解法：直接按合取式構(gòu)圖驗(yàn)證就行了

POJ 3683 - Priest John's Busiest Day(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3683
解法：n^2枚舉點(diǎn)之間的相容性構(gòu)圖，求解2-SAT

最大流問(wèn)題
變形很多，最小割最大流定理的理解是關(guān)鍵

POJ 1149 - PIGS(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1149
絕對(duì)經(jīng)典的構(gòu)圖題

POJ 1273 - Drainage Ditches(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
最大流入門

POJ 1459 - Power Network(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1459
基本構(gòu)圖

POJ 1637 - Sightseeing tour(Crazy)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1637
題意：求混合圖的歐拉跡是否存在
解法：無(wú)向邊任意定向，構(gòu)圖，詳建黑書(shū)P324

POJ 1815 - Friendship(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1815
題意：求最小點(diǎn)割
解法：拆點(diǎn)轉(zhuǎn)換為邊割
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/a521f230b06dea9fa9018e0e.html

POJ 1966 - Cable TV Network(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1966
題意：去掉多少點(diǎn)讓圖不連通
解法：任定一源點(diǎn)，枚舉匯點(diǎn)求點(diǎn)割集(轉(zhuǎn)換到求邊割)，求其中最小的點(diǎn)割

POJ 2112 - Optimal Milking(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2112
二分枚舉，最大流

POJ 2391 - Ombrophobic Bovines(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2391
題意：floyd, 拆點(diǎn)，二分枚舉
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/3e0006c4f73f0eaf8226acff.html

POJ 2396 - Budget(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2396
題意：有源匯的上下界可行流
解法：用矩陣-網(wǎng)絡(luò)流模型構(gòu)圖，然后拆邊
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/6449d82a64e15e3e5343c1ba.html
，最小割模型在競(jìng)賽中的應(yīng)用

POJ 2455 - Secret Milking Machine(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2455
二分枚舉，一般來(lái)說(shuō)需要寫對(duì)邊容量的更新操作而不是每次全部重新構(gòu)圖

POJ 2699 - The Maximum Number of Strong Kings(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2699
解法：枚舉人數(shù) + 最大流(感謝xpcnq_71大牛的建圖的提示)

POJ 2987 - Firing(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2987
題意：最大權(quán)閉包
解法：先邊權(quán)放大，第一問(wèn)總量-最大流，第二問(wèn)求最小割
相關(guān)：http://wywcgs.spaces.live.com/blog/cns!4D861A02A3382142!1109.entry?&_c02_owner=1
Profit(中等)
http://www.vijos.cn/Problem_Show.asp?id=1352
最大權(quán)閉包圖的特殊情況
ZOJ 2071 - Technology Trader 也是此類型，懶了沒(méi)做
http://acm.zju.edu.cn/show_problem.php?pid=2071

POJ 3084 - Panic Room(中等，好題)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3084
題意：略
解法：根據(jù)最小割建模

POJ 3155 - Hard Life(很挑戰(zhàn)一題)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3155
題意：最大密度子圖
解法：參數(shù)搜索 + 最大權(quán)閉合圖，A.V.Goldberg的論文(nb解法)
最小割模型在信息學(xué)競(jìng)賽中的應(yīng)用 一文中也有講

POJ 3189 - Steady Cow Assignment(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3189
題意：尋找最小的區(qū)間完成匹配
解法：這題充分說(shuō)明SAP的強(qiáng)大，純暴力可過(guò)。更好的方法是在枚舉區(qū)間的過(guò)程中不斷刪邊和加邊繼續(xù)網(wǎng)絡(luò)流過(guò)程

POJ 3204 - Ikki's Story I - Road Reconstruction(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3204
ZOJ 2532 - Internship(基礎(chǔ))
http://acm.zju.edu.cn/show_problem.php?pid=2532
題意：確定邊是否是某個(gè)割中的邊
解法：兩邊dfs求割, 或暴力枚舉(需要寫取消某條增廣路的操作(但數(shù)據(jù)弱，也許不取消也能混過(guò)))

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
題意：最小點(diǎn)權(quán)覆蓋

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
題意：滿足點(diǎn)容量限制的網(wǎng)絡(luò)流
解法：拆點(diǎn)把點(diǎn)容量轉(zhuǎn)換為邊容量，枚舉匯點(diǎn)

ZOJ 2587 - Unique Attack(較難)
http://acm.zju.edu.cn/show_problem.php?pid=2587
題意：確定最小割是否是唯一的
解法：得理解dfs求最小割算法的本質(zhì)

SPOJ 839 - Optimal Marks(難)
http://www.spoj.pl/problems/OPTM/
題意：略
解法：很經(jīng)典哦，見(jiàn)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)用流問(wèn)題
可以KM解的就不放在這里，另外，感覺(jué)除非很特殊的圖，一般用連續(xù)增廣路的算法就夠了

POJ 2175 - Evacuation Plan(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2175
題意：判斷是否給定解是最優(yōu)解，比較陰的一題
解法：根據(jù)給出的計(jì)劃構(gòu)造流，然后消且只消一次負(fù)圈

POJ 3422 - Kaka's Matrix Travels(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3422
題意：略
解法：拆點(diǎn)

POJ 3680 - Intervals(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3680
題意：略，這題還是蠻經(jīng)典
解法：discuss中比較詳細(xì)

SPOJ 371 - Boxes(簡(jiǎn)單)
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)用流，也可以最短路 + 最大流。

匹配問(wèn)題
正確理解KM算法是很重要的

這里我還要說(shuō)幾句：最正確解最小權(quán)匹配的辦法是用一個(gè)很大的數(shù)-當(dāng)前邊權(quán)值，而不是直接對(duì)邊權(quán)取反(這樣只能處理左右點(diǎn)相等的完全二分圖，即K(n, n)

以上有可能還是說(shuō)的有點(diǎn)問(wèn)題，以后補(bǔ)充

POJ 1486 - Sorting Slides(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1486
題意：二分圖的必須邊
解法：需正真理解最大匹配算法，詳見(jiàn)http://hi.baidu.com/kevin0602/blog/item/1d5be63b5bec9bec14cecb44.html

POJ 1904 - King's Quest(中等，好題)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1904
題意：求二分圖所有可能的匹配邊
解法：雖然最終不是用匹配算法，但需要理解匹配的思想轉(zhuǎn)換成強(qiáng)連通分量問(wèn)題。

POJ 2060 -Taxi Cab Scheme(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2060
題意：最小路徑覆蓋

POJ 2594 -Treasure Exploration(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2594
題意：可相交最小路徑覆蓋
解法：先傳遞閉包轉(zhuǎn)化下

POJ 3041 - Asteroids(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3041
POJ 2226 - Muddy Fields(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2226
題意：行列的覆蓋
解法：最小點(diǎn)集覆蓋 = 最大匹配

POJ 2195 - Going Home(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
題意：最小權(quán)值匹配
解法：KM算法

POJ 2400 - Supervisor, Supervisee(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2400
題意：輸出所有最小權(quán)匹配
解法：KM, 然后回溯解，汗，輸入的兩個(gè)矩陣居然是反過(guò)來(lái)的

POJ 2516 -Minimum Cost(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2516
題意：最小權(quán)值匹配或最小費(fèi)用流
解法：拆點(diǎn) + KM算法(只有正確的才能過(guò))，費(fèi)用流(ms錯(cuò)的可能也能過(guò))

POJ 3686 - The Windy's(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3686
題意：最小權(quán)值匹配
解法：拆點(diǎn),然后盡管用KM算法去水吧，數(shù)據(jù)其實(shí)弱得不得了 O(50 * 50 * 2500) -> 16ms
相關(guān)：http://hi.baidu.com/kevin0602/blog/item/2829dc01d7143b087bec2c97.html

SPOJ 412 - K-path cover(較難)
https://www.spoj.pl/problems/COVER/
題意：略
解法：很牛叉的一道匹配
相關(guān)：http://hi.baidu.com/roba/blog/item/c842fdfac10d24dcb48f31d7.html

SGU 206. Roads(較難)
http://acm.sgu.ru/problem.php?c0&problem=206
解法：經(jīng)典題目，也可以使用spoj 412那題的優(yōu)化

NP問(wèn)題
一般是搜索或dp解的

POJ 1419 - Graph Coloring(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1419
題意：圖的著色
解法：搜索，可惜題目的數(shù)據(jù)真是太弱了

POJ 2989 - All Friends(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2989
題意：極大團(tuán)數(shù)量
解法：開(kāi)始狂tle, 后來(lái)找了論文：Finding All Cliques of an Undirected Graph（Coen Bron & Joep Kerboscht）

ZOJ 1492 - Maximum Clique(基礎(chǔ))
http://acm.zju.edu.cn/show_problem.php?pid=1492
題意：圖的最大團(tuán)
解法：搜索，如果要求速度，可參考下相應(yīng)論文

其他
不能成大類的

POJ 1470 - Closest Common Ancestors(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1470
題意：LCA問(wèn)題
解法：tarjan或RMQ，另外輸入很惡心

POJ 1985 - Cow Marathon(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1985
題意：樹(shù)上的最長(zhǎng)路徑
解法：dp

POJ 1986 - Distance Queries(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
題意：LCA
解法：tarjan或RMQ

HOJ 11192 - Justice League(有趣的圖論)
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=11192&courseid=99

HOJ 11277 - New Island(有趣的圖論)
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=11277&courseid=109