图论练习题

ACM 图论 综合

第一部分：最短路

1.poj1062 昂贵的聘礼（中等）
此题是个经典题目；用Dijkstra即可；但是其中的等级处理需要一定的技巧；
要理解好那个等级制度；这个处理好，基本就是裸体Dijkstra；
8876888 bobo0906 1062 Accepted 268K 0MS C++ 2007B 2011-07-13 08:13:30
实现dijkstra。

2 poj1125 Stockbroker Grapevine（基本）
这个是简单Floyd，需要求出的是每对顶点之间的最短路径；
然后找到那个所需时间最小的那个人中的所需时间；
8878025 bobo0906 1125 Accepted 172K 0MS C++ 1187B 2011-07-13 10:24:00
实现floyd。

3，poj 1502 MPI Maelstrom（基本）
这题是邻接矩阵的Dijkstra就可以解决的； 直接水之；
8877226 bobo0906 1502 Accepted 236K 0MS C++ 1533B 2011-07-13 09:09:57
实现dijkstra+优先队列。类似的：POJ 3268 POJ 2387.注意重边。
8742168 bobo0906 2387 Accepted 276K 47MS C++ 1295B 2011-06-09 17:02:16
值得一提的是，这个用的系统堆实现的。
pop_heap。push_heap

4，poj 1511 Invitation Cards（中等）
有个地方注意一下就好了，每个志愿者回来的时候的最短路径；将原图的每条边反向一下，对端点1再来 SPFA就可以来； 正向图的结果+逆向图的结果就是所求；
8879358 bobo0906 1511 Accepted 39412K 1860MS C++ 2564B 2011-07-13 12:32:11
实现spfa

5，poj 1724 ROADS（中等）
题意是在一定的coins的限制下的最短路径
8884959 bobo0906 1724 Accepted 1040K 63MS C++ 1472B 2011-07-14 09:33:40
这题说是说dijkstra变形，其实就是一个bfs加优先队列。入队过的点还能入队才行。

6，poj1797 Heavy Transportation（中等） 从端点1到端点n的能够通过的最大载重；
8887272 bobo0906 1797 Accepted 1444K 297MS C++ 1777B 2011-07-14 13:46:25
一开始以为是个最大流水题，后来仔细看了一下，发现不是最大流，不过还是个水题。。。。
用Dijkstra变形一下，在松弛时改变一下松弛的条件就轻松水过了；但是我PE了3次。。。。

7，poj 1860 currency exchange（基本）
一个套汇问题，就是通过一系列的货币交换能够到达价值增加的目的；就是类似判断有没有负权回路；
8890040 bobo0906 1860 Accepted 420K 0MS C++ 2066B 2011-07-14 17:15:19
有个注意的地方就是要判断该源点在不在负环内而不是一旦有负环就return。
此题实现了SPFA判断负环。比较囧的是，0msAC的这个代码是不判负环的。。。POJ此题数据太弱。。。
类似的：poj 2240 poj 3259

8，poj 2253 Frogger（中等） Dijkstra的变形经典应用； 改变一下松弛时的条件；
8888253 bobo0906 2253 Accepted 768K 16MS C++ 2067B 2011-07-14 15:16:49
和poj1797类似，所求的正好相反，最囧的就是输出跟poj1797差一个“：”让我WA了很久。。。。

9，poj 2502 Subway（基本） 可以用Floyd来搞定，关键是哪个边的存储，存储后就是灰常简单的Floyd了；
8893864 bobo0906 2502 Accepted 688K 157MS C++ 1526B 2011-07-15 09:35:01

10，poj 3013 Big Christmas Tree（中等）
8895571 bobo0906 3013 Accepted 2944K 657MS C++ 1921B 2011-07-15 12:28:50
这个要有个重要的转化；首先price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
这句指出每条边的代价为该边所有子孙节点权值之和乘以该边的权值。换个角度就是每个节点的代价为该节点到根节点的所有边的权值乘以该节点的权值。（超INT，边要开大，无向图）

11，POJ 3635 - full tank?(中等)
题意：最短路变形，相当于另一种形式的拆点。或者用DP状态转移的思想就是，你可以选择买1L油转移到自己，你也可以在油正好够的时候转到别的点去。最后有100次查询，所以时间不是很快。据说可以用手写堆提速。
8912056 bobo0906 3635 Accepted 1728K 422MS C++ 2399B 2011-07-17 19:32:21

12、POJ 3621 - Sightseeing Cows(中等)
题意：求一个环路，欢乐值 / 总路径最大
解法：2分 参数搜索 + 最短路 （需要理解一个点一旦被扩展两次就有负环）
8921054 bobo0906 3621 Accepted 564K 516MS C++ 1669B 2011-07-18 17:50:35

13，poj 3037 Skiing（中等）这个题有点意思
对于每个点从该点出发的速度是恒定的，例如从a->b->c;则c出发的速度就是V*2^(A-B）*2^(B-C)=V*2^(A-C);
一开始以为边很少点也不多，准备用floyd的，后来仔细一下，虚了。。
8901544 bobo0906 3037 Accepted 1044K 188MS C++ 1886B 2011-07-16 10:14:41

14，poj 3159 Candies（基础）
8903010 bobo0906 3159 Accepted 2552K 1422MS C++ 1464B 2011-07-16 13:59:57
说实话，其实我没读懂题意，不过YY了一下，感觉像最短路，就过了，虽然与TLE只是擦肩而过。。。

15，poj 3377Ferry Lanes（中等）
8904861 bobo0906 3377 Accepted 55068K 1266MS C++ 3169B 2011-07-16 16:53:21
用宽搜加优先队列踩线过的。还可以用动态规划，据说是O（n）的算法。准备试试。

16，POJ3615 Cow hurdles (容易)
8905766 bobo0906 3615 Accepted 492K 438MS C++ 748B 2011-07-16 19:10:36
求点之间最大高度中的最小高度。floyd改下松弛条件

17，poj 3660 Cow Contest（中等）
这道题很有意思，有两种办法。一种是从该点正向dfs加反向dfs，所有点都遍历到的话，该牛就是确定排名的。
8681543 bobo0906 3660 Accepted 264K 63MS C++ 860B 2011-05-24 13:32:08
第二种方法就是用这个专题的东西啦，floyd。巧妙的用法就是，邻接矩阵中用0，1，2来分别存储关系不能确定，在之前，在之后；最后N^2遍历，出现除对角线外没有0出现就是确定关系的。
8905958 bobo0906 3660 Accepted 212K 16MS C++ 1351B 2011-07-16 19:40:35
毕竟floyd也不是什么高效算法。不过还是比第一种方法快不少啊。

18、POJ 2449 Remmarguts' Date(中等)经典问题：K短路 dijkstra+A*(rec)，方法很多
原来A*搜索就是bfs加预先队列优化。。。至于优先队列的权重就是估价函数。反正不算难题。以前还觉得K短路神秘。。
8934356 bobo0906 2449 Accepted 7492K 204MS C++ 2597B 2011-07-19 21:24:07

19、POJ 3463 - Sightseeing(中等)题意：最短路和比最短路大1的路的数量
8945990 bobo0906 3463 Accepted 396K 32MS C++ 3251B 2011-07-20 20:44:21
更新路径的时候记录最短路和次短路，同时记录他们的数量。如果路径比最短路短，更新最短路和次短路。路径跟最短路相同，增加最短路数量比最短路长的路径：如果比次短路短，更新次短路。跟次短路长度相同，增加次短路数量。检查次短路的路径长度是否比最短路大一，是就相加输出数量，否则仅输出最短路

20、POJ 3613 - Cow Relays(较难)题意：求经过K条边的最短路
解法：floyd + 倍增，整体就是一个DP经典题啊，dp[j]的定义就是我经过K条边的最短路。松弛K次，就是答案，但是这里的K很大，就要用到倍增思想了。
8952724 bobo0906 3613 Accepted 692K 125MS C++ 1645B 2011-07-21 15:07:31

****************************第一部分结束**************************************

第二部分：生成树

最小生成树基础4题，都是裸的最小生成树： POJ 1251 1258 1789 2485 分别用kruskal和prim过了一下这四题。也算是测了一下自己的模板。
kruskal适合稀疏图：
9277418 bobo0906 1251 Accepted 196K 0MS C++ 1248B 2011-09-04 22:49:49
9277323 bobo0906 1258 Accepted 252K 16MS C++ 1182B 2011-09-04 22:29:06
9277579 bobo0906 1789 Accepted 45524K 938MS C++ 1364B 2011-09-04 23:36:31
9277227 bobo0906 2485 Accepted 428K 250MS C++ 1207B 2011-09-04 22:11:10

prim适合稠密图：
9279394 bobo0906 2485 Accepted 648K 172MS C++ 1107B 2011-09-05 16:05:24
9279430 bobo0906 1789 Accepted 16368K 407MS C++ 1289B 2011-09-05 16:10:25

POJ 1679 - The Unique MST(基础)此题求最小生成树是否唯一，数据非常水。最老实的方法就是枚举最小生成树的某一条边求次小生成树，看次小生成树是否等于最小生成树。相等的话就是not unique。
不过不少人提出了一些其他高效的方法。
方法一、用PRIM算法来判断，当我们扩展一个节点u时，得到最小边min，然后判断在已经扩展的集合中是否有大于1条边权值等于min，如果有则最小生成树不唯一，反之唯一。（这个算法我实现了一下，能AC。效率如下：）
9282721 bobo0906 1679 Accepted 296K 16MS C++ 1309B 2011-09-06 09:45:39
但后来发现是错的！！！大囧啊。
反例：1 5 5 1 2 1 1 3 2 2 4 3 3 5 3 4 5 2
方法二：kruskal变形，复杂度为O(M+MlogM)。Kruscal贪心每次找出边权最小的边判断能否合并，假设找到了一条边权最小的边，其两个顶点所在集合的根节点分别为x和y，向后搜寻边权与当前边相同的边（即当前边权最小的边不唯一），若搜寻到的边两个顶点的根节点同样是x和y，则这两个集合合并就有了两种方法，此时就可以直接输出NotUnique!并退出。
9283324 bobo0906 1679 Accepted 248K 16MS C++ 1746B 2011-09-06 13:06:50
第二种方法其实我也不敢确定是否正确，不过没找到范例。求大家一起来讨论一下。

POJ 2728 - Desert King(中等)
题意：传说中的最优比率生成树。其实就是二分加prim。。。
完全图，kruskal各种TLE，完全图，还是prim水过的。据说可以用Dinkelbach(迭代法)
9289852 bobo0906 2728 Accepted 9656K 1250MS C++ 1682B 2011-09-07 17:52:59

POJ 2421 - Constructing Roads（基础）生成树水题，测测模板。
9425493 bobo0906 2421 Accepted 252K 47MS C++ 1275B 2011-10-12 14:56:51

第三部分：网络流

1、POJ 3041 - Asteroids(基础)网络流入门题
8002834 bobo0906 3041 Accepted 360K 0MS C++ 859B 2010-12-14 14:51:10

2、POJ 1459 最基本的最大流。
只需加一个源点和汇点，源点到发电站的距离为发电站的发电量，消费站到汇点的距离为消费站的消费量。
8824734 bobo0906 1459 Accepted 420K 94MS C++ 2165B 2011-07-04 22:24:05
网络流入门题（测自己写的模板）类似的：POJ 1273

3、POJ 3469 - Dual Core CPU(中等)题意：最小割
8824301 bobo0906 3469 Accepted 6056K 3735MS C++ 2025B 2011-07-04 21:38:52
简单题，实现自己的dinic高效模板（不过3735MS看上去依旧很慢哈、、、其实它给15000MS的）

4、POJ 2195 - Going Home(基础) 题意：最小权值匹配
8317788 bobo0906 2195 Accepted 500K 47MS C++ 1941B 2011-03-15 21:51:31
最小费用最大流（也可以用最小权值匹配模型做，尚未完成）

5、POJ 3155 - Hard Life(很挑战一题)
题意：最大密度子图解法：参数搜索 + 最大权闭合图，A.V.Goldberg的论文(nb解法)最小割模型在信息学竞赛中的应用 一文中也有讲
8851518 bobo0906 3155 Accepted 308K 297MS C++ 3113B 2011-07-09 08:45:03
实现最大权闭合图基本算法。
8843903 bobo0906 3155 Accepted 232K 79MS C++ 3153B 2011-07-07 22:00:37
实现最大密度子图改进算法

6、POJ 1815 - Friendship(中等) 题意：求最小点割解法：拆点转换为边割
8855373 bobo0906 1815 Accepted 456K 172MS C++ 3880B 2011-07-09 21:51:44
实现最小割求方案（求很多次dinic）
另一种沿残余网络退流降低复杂度的一直WA。

7、POJ 2987 - Firing(较难) 题意：最大权闭包解法：先边权放大，第一问总量-最大流，第二问求最小割
8830609 bobo0906 2987 Accepted 1740K 219MS C++ 2179B 2011-07-05 22:58:34
实现最大权闭合图

8、POJ 3084 - Panic Room(中等，好题) 根据最小割建模
8801347 bobo0906 3084 Accepted 188K 0MS C++ 1466B 2011-06-29 16:03:10

9、POJ 3308 - Paratroopers(较难)
8846614 bobo0906 3308 Accepted 244K 0MS C++ 2338B 2011-07-08 12:28:24
此题有意思的是题意。当然，模型也要好好YY。
product有乘积的意思，然后最大流不求和了，求乘积了，怎么办呢？
呵呵，答案是取对数建边。

10、2125 - Destroying The Graph(难) 题意：最小点权覆盖
8851476 bobo0906 2125 Accepted 296K 16MS C++ 2690B 2011-07-09 08:29:20
实现最小点权覆盖

11、POJ 2289 jamie's contact group 2分枚举答案加最大流，挺好的题.
8864657 bobo0906 2289 Accepted 8116K 329MS C++ 2556B 2011-07-11 13:34:42
类似的POJ 2455 此类题目想到二分就不难了，想不到的话。。。。（中）
9048636 bobo0906 2455 Accepted 1584K 297MS C++ 3129B 2011-08-01 10:12:10
类似的，POJ 2112 就当测模板用了。
9264074 bobo0906 2112 Accepted 624K 110MS C++ 2879B 2011-09-01 15:48:53

12、POJ 3204 - Ikki's Story I - Road Reconstruction(基础)
8960682 bobo0906 3204 Accepted 1344K 125MS C++ 2859B 2011-07-22 09:20:25
求割边数量，分别采取左集合染色和右集合染色的方法，然后枚举一开始的每条边，边的两端点颜色不同就是必要割边

13、POJ 2135 FARM TOUR (中等)
想到是网络流以后就简单了。建边的时候，之前考虑到网络流一定要有向边，而且题目中说边是无向的且只能走一次。这就很尴尬了，不知道怎么建边。实际上，直接正向反向都建边就行了，取最小费用最大流的时候，不可能重复走一条边的正向和反向。
9045843 bobo0906 2135 Accepted 828K 32MS C++ 2335B 2011-07-31 18:46:20
自己实现了一些最小费用最大流（值得注意的是费用流建翻边的时候，反边流量为0，费用为负费用）

14、POJ 2516 最小费用最大流，也是加一个源点和汇点，源点到仓库的容量为仓库的库存量（费用为0），商家到汇点的容量为商家的需求量（费用为0），仓库到商家间的容量为无穷大，费用为相应费用。这题想到这里还是会TLE的，伤不起。。一定要加个小优化，是什么呢？就是单个商品的需求不能大于供应。
9050597 bobo0906 2516 Accepted 1860K 2641MS C++ 3622B 2011-08-01 13:54:33
这题也可以用二分匹配来做。（未完成）

15、POJ 2226 - Muddy Fields(基础)
题意：行列的覆盖 解法：最小点集覆盖 = 最大匹配
9062732 bobo0906 2226 Accepted 6608K 32MS C++ 1442B 2011-08-02 17:36:4
用匈牙利算法做的，每一列（行）如果连着的算一个点，不连的每块算一个点
类似的：POJ 2060 -Taxi Cab Scheme(基础)题意：最小路径覆盖
9276631 bobo0906 2060 Accepted 436K 235MS C++ 1482B 2011-09-04 20:08:04

16、POJ 3422 - Kaka's Matrix Travels(中等)
解法：此题的精髓就是拆点，一个点自己到自己有一条流量为1，费用为点权值的边，还有一条流量无穷，费用为0
9068271 bobo0906 3422 Accepted 640K 47MS C++ 3250B 2011-08-03 12:17:00

17、POJ 2391 - Ombrophobic Bovines(中等)
题意：floyd+二分枚举最大流。
9077534 bobo0906 2391 Accepted 2284K 329MS C++ 4453B 2011-08-04 14:02:26
如果按照为这个题目列表刷，刷到这题时再做，不难。算是个经典的综合题。

18、POJ 1637 - Sightseeing tour(Crazy)
题意：求混合图的欧拉回路是否存在
解法：无向边任意定向，构图，算网络流是否满流，详建黑书P324
9096392 bobo0906 1637 Accepted 204K 16MS C++ 3792B 2011-08-06 20:22:47

19、POJ 1149 - PIGS(较难)绝对经典的构图
8520067 bobo0906 1149 Accepted 204K 0MS C++ 1730B 2011-04-21 09:59:51

20、POJ 3189 - Steady Cow Assignment(中等)
题意：寻找最小的区间完成匹配，我用的2分枚举区间网络流判定
160120 bobo0906 3189 Accepted 764K 63MS C++ 3488B 2011-08-14 18:45:30

21、POJ 3498 - March of the Penguins(中等)题意：满足点容量限制的网络流
解法：拆点把点容量转换为边容量，枚举汇点
9161650 bobo0906 3498 Accepted 680K 407MS C++ 4001B 2011-08-14 22:29:49

22、POJ 2175 - Evacuation Plan(中等)题意：判断是否给定解是最优解，根据给的计划构建网络，注意费用流中回边的建立费用为负，然后查看是否存在负权回路，“可行流x为最小费用流的充要条件是残量网络中不存在负费用增广圈”最后对给定的方案，加1或减1就行了。
9166220 bobo0906 2175 Accepted 400K 219MS C++ 3334B 2011-08-15 16:25:58

23、HDU 3987 Harry Potter and the Forbidden Forest
http://acm.hdu.edu.cn/showproblem.php?pid=3987
题意：求一个最小割方案，要求此方案是同类权值方案下，所需要割掉边数最少的。
方法1：watermalen队的：先做一遍最大流，把残余网络中流量不为0的边置为无穷大，流量为0 的置为1，再做一次最大流，所求值即是做少割边数量。
2011-08-31 16:31:23
Accepted
1006
171MS
6628KB
G++
watermelon
方法2：HJWAJ 那天YY的想法，后来仔细一想，果真也是对的：对于每一条边，建边的时候，容量为（原容量*一个比边数大的值M+1），然后做最大流，得到的结果mod那个比边数大的值M，就可以了。
4525121 2011-09-01 12:09:25 Accepted 3987 62MS 3472K 2544 B C++ WonderfloW
方法一为传统方法，第一次做最大流，把所有可能成为割的边找了出来，第二次，无穷大的边是不可能被割的，每可能割边流量为1，只能被割一次，就是找最小割的数量。巧妙的重用了残余网络。

方法二，首先可以知道，除了数据大，要用int64以为，其他无论是空间，还是时间上，比方法一都是要优的。然后不禁要问，为什么正确？
其实是无形中用到了数学中进位制的思想。把权重和边数用低位和高位区分起来，导致本来需要两次的操作，在一步就完成了。因为M够大，所以低位永远不可能影响到高位。高位确保了权值（割）最小的同时，低位确保了方案割的边数又是最少的。确实很巧妙。可惜当时比赛的时候有点放弃了，没好好去实现，int64没注意，WA了，以为算法不对，唉~

第四部分：连通性

POJ 1144 - NetWork（基础）
求割点的数量，刘汝佳黑书P285~P286页写的很好。就一遍DFS搞定。
9043731 bobo0906 1144 Accepted 192K 32MS C++ 1429B 2011-07-31 13:59:27

POJ 2553 - The Bottom of a Graph(基础)tarjan算法求强连通分量，然后把出度为0的连通块输出。
9210120 bobo0906 2553 Accepted 500K 63MS C++ 1838B 2011-08-22 12:51:38

POJ 2186 - Popular Cows(基础)
题意：强连通分量缩点图出度为0的点,最后判一下有两个连通块出度为0时不行就同时解决了图不联通的情况了。
9217981 bobo0906 2186 Accepted 756K 79MS C++ 1776B 2011-08-23 17:36:26

POJ 3207 - Ikki's Story IV - Panda's Trick(基础)
解法：2-sat入门题
9218855 bobo0906 3207 Accepted 1620K 16MS C++ 1887B 2011-08-23 20:28:00

第五部分：图论杂题

POJ 3249 - Test for Job(基础)
一开始想到枚举入度为0的点算最长路的，果断是这个结果。
9021062 bobo0906 3249 Time Limit Exceeded

C++ 2062B 2011-07-28 16:03:42

然后换成拓扑排序带点DP记忆化搜索的感觉算最长路，过了。有点值得注意的是，拓扑排序数据中可能有孤立的点。
9022209 bobo0906 3249 Accepted 10504K 2032MS C++ 1550B 2011-07-28 17:48:33

JLU 2760 JLUCPC (有点图论影子的记忆化搜索？)http://acm.jlu.edu.cn/joj/showproblem.php?pid=2760
关键是想出通过第一次DFS可以得到每个节点子树中所有结点权值之和，然后用一个神奇的公式就可以O（n）的复杂度算出所有结点的费用了。

POJ 3687 - Labeling Balls(中等)
解法：拓扑排序,注意重边（我是反向开始，用优先队列，对出度排序的）
9158797 bobo0906 3687 Accepted 352K 32MS C++ 1748B 2011-08-14 15:33:03