图论题目

最短路问题
此类问题类型不多，变形较少

POJ 2449 Remmarguts' Date(中等)
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(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3013
题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度
解法：Dijkstra

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

POJ 3613 - Cow Relays(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3613
题意：求经过N条边的最短路
解法：floyd + 倍增，贪心

POJ 3621 - Sightseeing Cows(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3621
题意：求一个环路，欢乐值 / 总路径最大
解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过)

POJ 3635 - full tank?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3635
题意：最短路变形
解法：广搜
相关：http://hi.baidu.com/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html

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

POJ 1639 - Picnic Planning(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1639
题意：顶点度数有限制的最小生成树
解法：贪心 + prim/kruskal

POJ 1679 - The Unique MST(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1679
题意：判断MST是否唯一
解法：prim就行，不过还是易错的题

POJ 2728 - Desert King(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2728
题意：所谓最优比率生成树
解法：参数搜索 + prim

POJ 3164 - Command Network(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3164
题意：最小树形图
解法：刘朱算法，这个考到的可能性比较小吧？

POJ 3522 - Slim Span(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3522
题意：求一颗生成树，让最大边最小边差值最小
解法：kruskal活用

连通性，度数，拓扑问题
此类问题主要牵扯到DFS，缩点等技巧

POJ 1236 - Network of Schools(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1236
题意：问添加多少边可成为完全连通图
解法：缩点，看度数

POJ 1659 - Frogs' Neighborhood(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1659
题意：根据度序列构造图
解法：贪心，详细证明参见havel定理

POJ 2553 - The Bottom of a Graph(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2553
POJ 2186 - Popular Cows(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2186
题意：强连通分量缩点图出度为0的点

POJ 2762 - Going from u to v or from v to u?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2762
题意：单向连通图判定
解法：缩点 + dp找最长链

POJ 2914 - Minimum Cut(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2914
题意：无向图最小割
解法：Stoer-Wagner算法，用网络流加枚举判定会挂

POJ 2942 - Knights of the Round Table(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2942
题意：求双联通分量(或称块)中是否含奇圈
解法：求出双连通分量后做黑白染色进行二分图图判定
相关：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
题意：添加多少条边可成为双向连通图
解法：把割边分开的不同分量缩点构树，看入度
建议对比下1236，有向图添加多少条边变成强连通图

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

POJ 3592 - Instantaneous Transference(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3592
解法：缩点，最长路，少人做的水题，注意细节

POJ 3687 - Labeling Balls(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3687
解法：拓扑排序

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

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

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(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3207
解法：简单的2-sat，不过其他方法更快

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

POJ 3678 - Katu Puzzle(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3678
解法：直接按合取式构图验证就行了

POJ 3683 - Priest John's Busiest Day(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3683
解法：n^2枚举点之间的相容性构图，求解2-SAT

最大流问题
变形很多，最小割最大流定理的理解是关键

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?contest=0&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?contest=0&problem=185
题意：求两条不想交的最短路径
解法：费用流，也可以最短路 + 最大流。

匹配问题
正确理解KM算法是很重要的

这里我还要说几句：最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n, n)

以上有可能还是说的有点问题，以后补充

POJ 1486 - Sorting Slides(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1486
题意：二分图的必须边
解法：需正真理解最大匹配算法，详见http://hi.baidu.com/kevin0602/blog/item/1d5be63b5bec9bec14cecb44.html

POJ 1904 - King's Quest(中等，好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1904
题意：求二分图所有可能的匹配边
解法：虽然最终不是用匹配算法，但需要理解匹配的思想转换成强连通分量问题。

POJ 2060 -Taxi Cab Scheme(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2060
题意：最小路径覆盖

POJ 2594 -Treasure Exploration(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2594
题意：可相交最小路径覆盖
解法：先传递闭包转化下

POJ 3041 - Asteroids(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3041
POJ 2226 - Muddy Fields(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2226
题意：行列的覆盖
解法：最小点集覆盖 = 最大匹配

POJ 2195 - Going Home(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
题意：最小权值匹配
解法：KM算法

POJ 2400 - Supervisor, Supervisee(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2400
题意：输出所有最小权匹配
解法：KM, 然后回溯解，汗，输入的两个矩阵居然是反过来的

POJ 2516 -Minimum Cost(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2516
题意：最小权值匹配或最小费用流
解法：拆点 + KM算法，费用流

POJ 3686 - The Windy's(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3686
题意：最小权值匹配
解法：拆点,然后尽管用KM算法去水吧，数据其实弱得不得了 O(50 * 50 * 2500) -> 16ms
相关：http://hi.baidu.com/kevin0602/blog/item/2829dc01d7143b087bec2c97.html

SPOJ 412 - K-path cover(较难)
https://www.spoj.pl/problems/COVER/
题意：略
解法：很牛叉的一道匹配
相关：http://hi.baidu.com/roba/blog/item/c842fdfac10d24dcb48f31d7.html

SGU 206. Roads(较难)
http://acm.sgu.ru/problem.php?contest=0&problem=206
解法：经典题目，也可以使用spoj 412那题的优化

NP问题
一般是搜索或dp解的

团问题（对偶问题为最大独立集问题）：

主要是最大团和极大团问题。团问题毕竟是NP的，因此只能通过搜索和剪枝来做。下面给出了最大团、极大团的资料

最大团问题：http://bchine.com/mjmjmtl/wp-content/uploads/2010/03/MaxClique.pdf
极大团问题：http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

POJ 1419

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

由于任意两个黑色的点不能相连，因此就是找最大独立集，逆问题就是找最大团。

由于数据比较弱，也可以用搜索解，伪代码如下：

void dfs(int i, int cur) {
   if(i== n) {
       if(cur > ans)  保存新的答案
       return;
   } 
   dfs(i+1, cur); //对应这个点为白色的
   if(cnt[i] == 0) {//装的那些没有点和我相连。
      for(所有和i相邻的点b)       
      cnt[b] ++;//以后和我相连的入度-1
      stack[cur] = i;                 
      dfs(i+1, cur + 1);
      for(所有和i相邻的点b)       
      cnt[b] ++;//恢复现场
   }
}

POJ 3692

LCA-RMQ问题：

这两个问题解法及其转化在刘汝佳的《高级数据结构》那个pdf上面讲的很明白。

离线LCA解法：tarjan算法

离线RMQ解法：ST算法最快(查询O(1))，线段树也可以(查询O(lg(n)))

LCA转RMQ：一次深度优先遍历，记录欧拉序列、深度序列、某个点dfs时第一次出现的位置，然后转为RMQ就可以了（深度序列的最小查询）。

RMQ转LCA：构造笛卡尔树，可以在O(n)时间内转化，非常优美~~~~

POJ 1470

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

比较普通的LCA，编码有点麻烦而已，还有输入有点恶心，最好getchar读入数字。

POJ 1984

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

一开始把所有的坐标都给算法，然后输出的时候，借用下并查集就ok了，注意“I is the index (1 <= I <= M) in the data after which Bob asks the query”是升序的！！！这样就好办了。

POJ 1985

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

树上的最长路径，dfs式dp就可以了！

POJ 1986

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

普通的LCA，c++ tle，g++ AC，不解释。

POJ 1987

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

找树中路径长度小于等于K的个数。

有关笛卡尔树的题：

sgu 155

http://acm.sgu.ru/problem.php?contest=0&problem=155

poj 2201

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

这两道题是一道题。一定可以构造笛卡尔树，先按照关键字k进行排序，然后构造笛卡尔树，这样对于k来说是Binary Search Tree，对于a来说是Cartesian Tree。这一点利用了笛卡尔树中序遍历是原数组的性质！

其他
不能成大类的

POJ 1470 - Closest Common Ancestors(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1470
题意：LCA问题
解法：tarjan或RMQ，另外输入很恶心

POJ 1985 - Cow Marathon(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1985
题意：树上的最长路径
解法：dp

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

网络流补充

网络流是ACM里非常重要的一大块,变形非常灵活,这些天仅仅只是做了一点点题目,几个经典模型,冰山一角而已.
图论可不是练两天就能掌握的,所以也就放弃了一口吃成胖子的想法,打一场持久战,有空的时候更新几道并在下边写点解题报告,所以暂时不可能成为一篇非常完整的整理
所以我在下文加了几个相关链接,都是大牛们的整理,并且也有这对题目的相关分析…

网络流的题如果直接看分析就浪费了最重要的思考过程,所以先隐藏建图,选中之后出现分析

1. hdu3046 Pleasant sheep and big big wolf

   1连源点,2连汇点,容量无限,各个格子间连边容量为1,求最小割

2. hust1024 dance party

   拆点,二分答案—建图:源点到男孩1的边容量为二分的值,女孩1到汇点的边容量为二分的值,男孩1到喜欢女孩1的边容量为1,男孩1到男孩2的边容量为k,男孩2到不喜欢女孩2的边容量为1,女孩2到女孩1的边容量为k,求最大流

3. hdu1569 方格取数(2)

   经典题目,按国际象棋黑白染色,源点到黑点容量为数字,黑点到它周围的白点容量为无穷,白点到汇点容量为数字,最后答案为总值减去最小割

4. pku3469 Dual Core CPU

   源点连到点的容量为Ai,点到汇点的容量为Bi,对于m个关系建容量为w的双向边

5. hdu2732 Leapin’ Lizard

   先抱怨下着题的英语写的太恶心了…拆点,每个点容量为它的数字,让后按d的距离可以跳到的点建容量无穷的边,可以跳出去的点和汇点建容量无穷的边,源点和每个L建容量为1的边

6. sug438 The Glorious Karlutka River 

   经典题目,加上时间限定条件,并且容量在点上,需要拆点,假设答案时间是T,那么每个点都要拆成2*T个点
   具体建法:S->SS为人数,SS->V无穷,U_T,1->U_T,2为点的容量,U_T-1,2->V_T,1无穷,U_T-1,2->U_T,1无穷,U_T-1,2->T无穷
   效率关键是看怎么建图个方案和答案T的枚举,我用了四个方法,时间效率比较如下:
   sap(邻接表)按时间从小到大遍历,每次都重新建图重新增广2173MS
   sap(邻接表)二分时间,每次都重新建图重新增广409MS
   EK(邻接表)按时间从小到大,但是每次增加2*n个点后在原来的基础上增广47MS
   sap(邻接表)按时间从小到大,但是每次增加2*n个点后在原来的基础上增广(但是dis和gap初始化)772MS
   (这里sap比EK还慢,也许是因为每次推的时候dis和gap清空了(不初始化的话答案不出来),所以推的很慢,不知道有没有更好的算法)

7. sug176 Flow construction

   经典题目,有上下界的最小流,做法入下
   1.in[v]表示以v为终点的边的下界之和,out[u]表示以u为起点的边的下界之和
   2.虚拟出ss,tt,连(ss,in[v])和(out[u],tt)
   3.做一次maxflow(ss,tt)
   4.加一条t->s的inf边
   5.再做一次maxflow(ss,tt)
   6.如果两次maxflow之和 < in之和,则不存在可行流
   7.最后答案为f[t -> s]既inf – 残余[t -> s]

8. hust1342 Cheat Secretly

   同上题,前几天比赛被这题虐了…赤裸裸的下界最小流,学了后顺秒

9. hdu1733 Escape

   本质和sug438 The Glorious Karlutka River =)一样,建图比那那稍微烦一点点..

10. pku2396 Budget

    虚拟个源点,流入col_i的上下界为col[i],col_i到点ij的流量为inf,点ij到row_j的上下界为自己本身的限制,row_j到虚拟汇点的上下界为row[j],求满足条件可行流
    和最小流的一样建图,然后做一次maxflow,如果和in的总量相同则有解,输出每个点的流量

11. sug454 Kakuro

    没看到第二个条件.每行里不能有相同的数字,于是悲剧了,构造不出这种限制,不能用最大流做,试试用DLX

12. hdu2883 kebab

    很巧的一道题目,附出题人的解题报告:
    将所有的到达时间和结束时间按升序排序，得到 x <= 2n-1 个时间区间。建立网络流模型：s为源，t为汇，每个顾客i作为一个结点并连边（s, i, ni*ti），每个区间j作为一个结点并连边(j, t, (ej-sj)*M)，其中sj, ej分别表示区间j的起始时间和终止时间。对任意顾客i和区间j，若 [sj, ej] 完全包含在 [si, ei] 之中，则连边(i, j, INF)。若最大流等于 ∑ni*ti 则是 Yes，否则是 No。

13. hdu3061 Battle

    经典题目,附出题人的解题报告:
    这是一个最小割的模型，具体的构图是：
    从源点连接正权的点，流量上限为该点的权值；
    从负权点连接汇点，流量上限为该点权值的绝对值；
    所有具有拓扑关系的点直接，从st连接end一条INF上限的边；
    求出最大流，最后用所有正权点的和减去最大流（最小割），便是答案。
    具体请参见07年的集训队论文《最小割模型在信息学竞赛中的应用》。

相关链接:

• 我的网络流模板
• hust博客整理的最大流题
• zhouxc2007整理的非常全的图论题
• McFn整理的PKU图论分类
•  

• 全局相关文章
• 相关文章