POJ 2449 Remmarguts' Date(中等) ?AC

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

题意：经典问题：K短路

解法：dijkstra+A*(rec)，方法很多

相关：http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144

该题亦放在搜索推荐题中

POJ 3013 - Big Christmas Tree(基础) ?AC

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

题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度

解法：Dijkstra

POJ 3463 - Sightseeing(中等) ?AC

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

题意：最短路和比最短路大1的路的数量

解法：需要真正理解dijkstra

POJ 3613 - Cow Relays(较难) ?AC

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

题意：求经过N条边的最短路

解法：floyd + 倍增，贪心

POJ 3621 - Sightseeing Cows(中等) ?AC

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

题意：求一个环路，欢乐值 / 总路径最大

解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过)

POJ 3635 - full tank?(中等) ?AC

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

题意：最短路变形

解法：广搜

相关：http://hi.baidu.com/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html

生成树问题

基本的生成树就不放上来了

POJ 1639 - Picnic Planning(较难)?AC

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

题意：顶点度数有限制的最小生成树

解法：贪心 + prim/kruskal

POJ 1679 - The Unique MST(基础) ?AC

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

题意：判断MST是否唯一

解法：prim就行，不过还是易错的题

POJ 2728 - Desert King(中等) ?AC

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

题意：所谓最优比率生成树

解法：参数搜索 + prim

POJ 3164 - Command Network(难)?AC

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

题意：最小树形图

解法：刘朱算法，这个考到的可能性比较小吧？

POJ 3522 - Slim Span(基础) ?AC

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

题意：求一颗生成树，让最大边最小边差值最小

解法：kruskal活用

连通性，度数，拓扑问题

此类问题主要牵扯到DFS，缩点等技巧

POJ 1236 - Network of Schools(基础) ?AC

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

题意：问添加多少边可成为完全连通图

解法：缩点，看度数

POJ 1659 - Frogs' Neighborhood(基础)?AC

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

题意：根据度序列构造图

解法：贪心，详细证明参见havel定理

POJ 2553 - The Bottom of a Graph(基础) ?AC ?（好题）

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

出度为0的强连通分量的所有的点

POJ 2186 - Popular Cows(基础)??AC ?（好题）

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

题意：强连通分量缩点图出度为0的点

POJ 2762 - Going from u to v or from v to u?(中等)?AC

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

题意：单向连通图判定

解法：缩点 + dp找最长链 (我是用 缩点+ 欧拉路判断，最后证明这方法是错的)

POJ 2914 - Minimum Cut(难)?AC ?（难）

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

题意：无向图最小割

解法：Stoer-Wagner算法，用网络流加枚举判定会挂

POJ 2942 - Knights of the Round Table(难)?AC

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

题意：求双联通分量(或称块)中是否含奇圈

解法：求出双连通分量后做黑白染色进行二分图图判定

相关：http://hi.baidu.com/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.html

POJ 3177 - Redundant Paths(中等)?AC

http://acm.pku.edu.cn/JudgeOnline/problem?id=3177?（和3352一样）

题意：添加多少条边可成为双向连通图（任意两点间有两条不共边的路径）

解法：把割边分开的不同分量缩点构树，看入度

公式： 入度为1的leaf个数， ( leaf + 1 ) / 2

POJ 3352 - Road Construction(中等)?AC

http://acm.pku.edu.cn/JudgeOnline/problem?id=3352?（和3177一样）

题意：添加多少条边可成为双向连通图（当删除任意一条边的时候，图还保持连通性）

解法：把割边分开的不同分量缩点构树，看入度?( leaf + 1 ) / 2

建议对比下1236，有向图添加多少条边变成强连通图

POJ 3249 - Test for Job(基础)

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

解法：bfs / dfs + dp

POJ 3592 - Instantaneous Transference(基础)?AC

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

解法：缩点，最长路，少人做的水题，注意细节 （和 3160 类似）

POJ 3687 - Labeling Balls(中等) ?AC ?（莫名其妙，有空再重新看）

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

解法：拓扑排序

POJ 3694 - Network(中等)?AC

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

解法：双连通分量+并查集

2-SAT问题

此类问题理解合取式的含义就不难

POJ 2723 - Get Luffy Out(中等)?AC （好题）

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

解法：二分 + 2-SAT判定

POJ 2749 - Building roads(较难)?AC

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

解法：二分 + 2-SAT判定

POJ 3207 - Ikki's Story IV - Panda's Trick(基础)?AC

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

解法：简单的2-sat，不过其他方法更快

POJ 3648- Wedding(中等)?AC

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

解法：用2-sat做会比较有意思，但是暴搜照样0ms

POJ 3678 - Katu Puzzle(基础)?AC?

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

解法：直接按合取式构图验证就行了（本质）

POJ 3683 - Priest John's Busiest Day(中等)?AC

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

解法：n^2枚举点之间的相容性构图，求解2-SAT (要求输出方案)

POJ 2296?Map Labeler?(中等) (第七道)AC

? ? ? ? http://poj.org/problem?id=2296?