网络流题目集锦

1、.网络流题目集锦（转）(2010-02-07 18:00:40) 转载标签： 杂谈分类：ACM最大流POJ 1273 Drainage DitchesPOJ 1274 The Perfect Stall (二分图匹配)POJ 1698 Alices ChancePOJ 1459 Power NetworkPOJ 2112 Optimal Milking (二分)POJ 2455 Secret Milking Machine (二分)POJ 3189 Steady Cow Assignment (枚举)POJ 1637 Sightseeing tour (混合图欧拉回路)POJ 3498 Mar

2、ch of the Penguins (枚举汇点)POJ 1087 A Plug for UNIXPOJ 1149 Pigs (构图题)ZOJ 2760 How Many Shortest Path (边不相交最短路的条数)POJ 2391 Ombrophobic Bovines (必须拆点，否则有BUG)WHU 1124 Football Coach (构图题)SGU 326 Perspective (构图题，类似于 WHU 1124)UVa 563 CrimewaveUVa 820 Internet BandwidthPOJ 3281 Dining (构图题)POJ 3436 ACM Co

3、mputer FactoryPOJ 2289 Jamies Contact Groups (二分)SGU 438 The Glorious Karlutka River =) (按时间拆点)SGU 242 Students Morning (输出一组解)SGU 185 Two shortest (Dijkstra 预处理，两次增广，必须用邻接阵实现，否则 MLE)HOJ 2816 Power LinePOJ 2699 The Maximum Number of Strong Kings (枚举+构图)ZOJ 2332 GemsJOJ 2453 Candy (构图题)SOJ3312 Stockh

4、olm KnightsSOJ3353 Total FlowSOJ2414 Leapin Lizards 最小割SOJ3106 Dual Core CPUSOJ3109 Space flightSOJ3107 SelectSOJ3185 Black and whiteSOJ3254 Rain and FgjSOJ3134 windy和水星 - 水星交通HOJ 2634 How to earn moreZOJ 2071 Technology Trader (找割边)HNU 10940 CoconutsZOJ 2532 Internship (找关键割边)POJ 1815 Friendship (字

5、典序最小的点割集)POJ 3204 Ikkis Story I - Road Reconstruction (找关键割边)POJ 3308 ParatroopersPOJ 3084 Panic RoomPOJ 3469 Dual Core CPUZOJ 2587 Unique Attack (最小割的唯一性判定)POJ 2125 Destroying The Graph (找割边)ZOJ 2539 Energy MinimizationTJU 2944 Mussy Paper (最大权闭合子图)POJ 1966 Cable TV Network (无向图点连通度)HDU 1565 方格取数(1

6、) (最大点权独立集)HDU 1569 方格取数(2) (最大点权独立集)POJ 2987 Firing (最大权闭合子图)SPOJ 839 Optimal Marks (将异或操作转化为对每一位求最小割)HOJ 2811 Earthquake Damage (最小点割集)2008 Beijing Regional Contest Problem A Destroying the bus stations ( BFS 预处理 )(http:/acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4322)ZOJ 2676 Netw

7、ork Wars (参数搜索)POJ 3155 Hard Life (参数搜索)ZOJ 3241 Being a Hero有上下界ZOJ 2314 Reactor Cooling (无源汇可行流)POJ 2396 Budget (有源汇可行流)SGU 176 Flow Construction (有源汇最小流)ZOJ 3229 Shoot the Bullet (有源汇最大流)HDU 3157 Crazy Circuits (有源汇最小流)最小费用流HOJ 2715 Matrix3HOJ 2739 The Chinese Postman ProblemPOJ 2175 Evacuation P

8、lan (消一次负圈)POJ 3422 Kakas Matrix Travels (与 Matrix3 类似)POJ 2516 Minimum Cost (按物品种类多次建图)POJ 2195 Going HomeBUAA 1032 Destroying a PaintingPOJ 2400 Supervisor, Supervisee (输出所有最小权匹配)POJ 3680 IntervalsHOJ 2543 Stone IVPOJ 2135 Farm TourBASHU2445 餐巾问题-onmylove原创最大流题目：TC：Single Round Match 200 Round 1 D

9、ivision I, Level ThreeSingle Round Match 236 Round 1 Division I, Level ThreeSingle Round Match 399 Round 1 Division I, Level Three同Hoj1024: /thx/problem.php?id=10242003 TCO Semifinal Round 4 Division I, Level Three2004 TCCC Championship Round Division I, Level Three2005 TCO Spon

10、sor Track Round 3 Division I, Level One混合图的欧拉回路Poj1637: /JudgeOnline/problem?id=1637zju1992：/show_problem.php?pid=1992 求增广边：Poj3204：/JudgeOnline/problem?id=3204类似：Hoj1082: /thx/problem.php?cid=1017&pid=6pku图论、网络流入门题总结、汇

11、总(2009-10-07 23:25:25) 转载标签： 杂谈分类：acm_图论题POJ 2449 Remmarguts Date(中等)/JudgeOnline/problem?id=2449题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很多相关：/JudgeOnline/showcontest?contest_id=1144该题亦放在搜索推荐题中POJ 3013 - Big Christmas Tree(基础)/JudgeOnline/problem?

12、id=3013题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度解法：DijkstraPOJ 3463 - Sightseeing(中等)/JudgeOnline/problem?id=3463题意：最短路和比最短路大1的路的数量解法：需要真正理解dijkstraPOJ 3613 - Cow Relays(较难)/JudgeOnline/problem?id=3613题意：求经过N条边的最短路解法：floyd + 倍增，贪心POJ 3621 - Sightseeing Cows(中等)http:/a

13、/JudgeOnline/problem?id=3621题意：求一个环路，欢乐值 / 总路径最大解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过)POJ 3635 - full tank?(中等)/JudgeOnline/problem?id=3635题意：最短路变形解法：广搜相关：/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html生成树问题基本的生成树就不放上来了POJ 1639 - Picnic Plann

14、ing(较难)/JudgeOnline/problem?id=1639题意：顶点度数有限制的最小生成树解法：贪心 + prim/kruskalPOJ 1679 - The Unique MST(基础)/JudgeOnline/problem?id=1679题意：判断MST是否唯一解法：prim就行，不过还是易错的题POJ 2728 - Desert King(中等)/JudgeOnline/problem?id=2728题意：所谓最优比率生成树解法：参数搜索 + primPO

15、J 3164 - Command Network(难)/JudgeOnline/problem?id=3164题意：最小树形图解法：刘朱算法，这个考到的可能性比较小吧？POJ 3522 - Slim Span(基础)/JudgeOnline/problem?id=3522题意：求一颗生成树，让最大边最小边差值最小解法：kruskal活用连通性，度数，拓扑问题此类问题主要牵扯到DFS，缩点等技巧POJ 1236 - Network of Schools(基础)/JudgeOnl

16、ine/problem?id=1236题意：问添加多少边可成为完全连通图解法：缩点，看度数POJ 1659 - Frogs Neighborhood(基础)/JudgeOnline/problem?id=1659题意：根据度序列构造图解法：贪心，详细证明参见havel定理POJ 2553 - The Bottom of a Graph(基础)/JudgeOnline/problem?id=2553POJ 2186 - Popular Cows(基础)/JudgeOnline/

17、problem?id=2186题意：强连通分量缩点图出度为0的点POJ 2762 - Going from u to v or from v to u?(中等)/JudgeOnline/problem?id=2762题意：单向连通图判定解法：缩点 + dp找最长链POJ 2914 - Minimum Cut(难)/JudgeOnline/problem?id=2914题意：无向图最小割解法：Stoer-Wagner算法，用网络流加枚举判定会挂POJ 2942 - Knights of the Round Table

18、(难)/JudgeOnline/problem?id=2942题意：求双联通分量(或称块)中是否含奇圈解法：求出双连通分量后做黑白染色进行二分图图判定相关：/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.htmlPOJ 3177 - Redundant Paths(中等)/JudgeOnline/problem?id=3177POJ 3352 - Road Construction(中等)/Judge

19、Online/problem?id=3352题意：添加多少条边可成为双向连通图解法：把割边分开的不同分量缩点构树，看入度建议对比下1236，有向图添加多少条边变成强连通图POJ 3249 - Test for Job(基础)/JudgeOnline/problem?id=3249解法：bfs / dfs + dpPOJ 3592 - Instantaneous Transference(基础)/JudgeOnline/problem?id=3592解法：缩点，最长路，少人做的水题，注意细节POJ 3687 - La

20、beling Balls(中等)/JudgeOnline/problem?id=3687解法：拓扑排序POJ 3694 - Network(中等)/JudgeOnline/problem?id=3694解法：双连通分量+并查集2-SAT问题此类问题理解合取式的含义就不难POJ 2723 - Get Luffy Out(中等)/JudgeOnline/problem?id=2723POJ 2749 - Building roads(较难)

21、/JudgeOnline/problem?id=2749解法：二分 + 2-SAT判定POJ 3207 - Ikkis Story IV - Pandas Trick(基础)/JudgeOnline/problem?id=3207解法：简单的2-sat，不过其他方法更快POJ 3648- Wedding(中等)/JudgeOnline/problem?id=3648解法：用2-sat做会比较有意思，但是暴搜照样0msPOJ 3678 - Katu Puzzle(基础)/Jud

22、geOnline/problem?id=3678解法：直接按合取式构图验证就行了POJ 3683 - Priest Johns Busiest Day(中等)/JudgeOnline/problem?id=3683解法：n2枚举点之间的相容性构图，求解2-SAT最大流问题变形很多，最小割最大流定理的理解是关键POJ 1149 - PIGS(较难)/JudgeOnline/problem?id=1149绝对经典的构图题POJ 1273 - Drainage Ditches(基础).c

23、n/JudgeOnline/problem?id=1273最大流入门POJ 1459 - Power Network(基础)/JudgeOnline/problem?id=1459基本构图POJ 1637 - Sightseeing tour(Crazy)/JudgeOnline/problem?id=1637题意：求混合图的欧拉迹是否存在解法：无向边任意定向，构图，详建黑书P324POJ 1815 - Friendship(中等)/JudgeOnline/problem?i

24、d=1815题意：求最小点割解法：拆点转换为边割相关：/zfy0701/blog/item/a521f230b06dea9fa9018e0e.htmlPOJ 1966 - Cable TV Network(中等)/JudgeOnline/problem?id=1966题意：去掉多少点让图不连通解法：任定一源点，枚举汇点求点割集(转换到求边割)，求其中最小的点割POJ 2112 - Optimal Milking(基础)/JudgeOnline/problem?id=2112二分枚

25、举，最大流POJ 2391 - Ombrophobic Bovines(中等)/JudgeOnline/problem?id=2391题意：floyd, 拆点，二分枚举相关：/zfy0701/blog/item/3e0006c4f73f0eaf8226acff.htmlPOJ 2396 - Budget(中等)/JudgeOnline/problem?id=2396题意：有源汇的上下界可行流解法：用矩阵-网络流模型构图，然后拆边相关：/zfy0

26、701/blog/item/6449d82a64e15e3e5343c1ba.html，最小割模型在竞赛中的应用POJ 2455 - Secret Milking Machine(基础)/JudgeOnline/problem?id=2455二分枚举，一般来说需要写对边容量的更新操作而不是每次全部重新构图POJ 2699 - The Maximum Number of Strong Kings(较难)/JudgeOnline/problem?id=2699解法：枚举人数 + 最大流(感谢xpcnq_71大牛的建图的

27、提示)POJ 2987 - Firing(较难)/JudgeOnline/problem?id=2987题意：最大权闭包解法：先边权放大，第一问总量-最大流，第二问求最小割相关：/blog/cns!4D861A02A3382142!1109.entry?&_c02_owner=1Profit(中等)/Problem_Show.asp?id=1352最大权闭包图的特殊情况ZOJ 2071 - Technology Trader 也是此类型，懒了没做http:/acm

28、./show_problem.php?pid=2071POJ 3084 - Panic Room(中等，好题)/JudgeOnline/problem?id=3084题意：略解法：根据最小割建模POJ 3155 - Hard Life(很挑战一题)/JudgeOnline/problem?id=3155题意：最大密度子图解法：参数搜索 + 最大权闭合图，A.V.Goldberg的论文(nb解法)最小割模型在信息学竞赛中的应用 一文中也有讲POJ 3189 - Steady Cow Assignm

29、ent(中等)/JudgeOnline/problem?id=3189题意：寻找最小的区间完成匹配解法：这题充分说明SAP的强大，纯暴力可过。更好的方法是在枚举区间的过程中不断删边和加边继续网络流过程POJ 3204 - Ikkis Story I - Road Reconstruction(基础)/JudgeOnline/problem?id=3204ZOJ 2532 - Internship(基础)/show_problem.php?pid=2532题意：确定边是否是某个

30、割中的边解法：两边dfs求割, 或暴力枚举(需要写取消某条增广路的操作(但数据弱，也许不取消也能混过)POJ 3308 - Paratroopers(较难)/JudgeOnline/problem?id=3308POJ 2125 - Destroying The Graph(难)/JudgeOnline/problem?id=2125题意：最小点权覆盖POJ 3469 - Dual Core CPU(中等)/JudgeOnline/problem?id=3469题意：最小割P

31、OJ 3498 - March of the Penguins(中等)/JudgeOnline/problem?id=3498题意：满足点容量限制的网络流解法：拆点把点容量转换为边容量，枚举汇点ZOJ 2587 - Unique Attack(较难)/show_problem.php?pid=2587题意：确定最小割是否是唯一的解法：得理解dfs求最小割算法的本质SPOJ 839 - Optimal Marks(难)http:/www.spoj.pl/problems/OPTM/题意：略解法：很经典哦，见amber

32、的集训队论文，根据标号的每一位求最小割SGU 326 - Perspective(中等)http:/acm.sgu.ru/problem.php?c0&problem=326比较经典的构图法费用流问题可以KM解的就不放在这里，另外，感觉除非很特殊的图，一般用连续增广路的算法就够了POJ 2175 - Evacuation Plan(中等)/JudgeOnline/problem?id=2175题意：判断是否给定解是最优解，比较阴的一题解法：根据给出的计划构造流，然后消且只消一次负圈POJ 3422 - Kakas Matrix Travels(中等)ht

33、tp://JudgeOnline/problem?id=3422题意：略解法：拆点POJ 3680 - Intervals(较难)/JudgeOnline/problem?id=3680题意：略，这题还是蛮经典解法：discuss中比较详细SPOJ 371 - Boxes(简单)http:/www.spoj.pl/problems/BOXES/题意：略解法：费用流，但似乎有比网络流更好的做法SGU 185 - Two shortest(中等)http:/acm.sgu.ru/problem.php?c0&problem=185

34、题意：求两条不想交的最短路径解法：费用流，也可以最短路 + 最大流。匹配问题正确理解KM算法是很重要的这里我还要说几句：最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n, n)以上有可能还是说的有点问题，以后补充POJ 1486 - Sorting Slides(中等)/JudgeOnline/problem?id=1486题意：二分图的必须边解法：需正真理解最大匹配算法，详见/kevin0602/blog/item/1d5be63b5bec9be

35、c14cecb44.htmlPOJ 1904 - Kings Quest(中等，好题)/JudgeOnline/problem?id=1904题意：求二分图所有可能的匹配边解法：虽然最终不是用匹配算法，但需要理解匹配的思想转换成强连通分量问题。POJ 2060 -Taxi Cab Scheme(基础)/JudgeOnline/problem?id=2060题意：最小路径覆盖POJ 2594 -Treasure Exploration(中等)/JudgeOnline/probl

36、em?id=2594题意：可相交最小路径覆盖解法：先传递闭包转化下POJ 3041 - Asteroids(基础)/JudgeOnline/problem?id=3041POJ 2226 - Muddy Fields(基础)/JudgeOnline/problem?id=2226题意：行列的覆盖解法：最小点集覆盖 = 最大匹配POJ 2195 - Going Home(基础)/JudgeOnline/problem?id=2195题意：最小权值匹配解法：KM算法POJ 240

37、0 - Supervisor, Supervisee(中等)/JudgeOnline/problem?id=2400题意：输出所有最小权匹配解法：KM, 然后回溯解，汗，输入的两个矩阵居然是反过来的POJ 2516 -Minimum Cost(中等)/JudgeOnline/problem?id=2516题意：最小权值匹配或最小费用流解法：拆点 + KM算法(只有正确的才能过)，费用流(ms错的可能也能过)POJ 3686 - The Windys(较难)/JudgeOnline/problem?id=3686题意：最小权值匹配解法：拆点,然后尽管用KM算法去水吧，数据其实弱得不得了 O(50 * 50 * 2500) - 16ms相关：/kevin0602/blog/item/2829dc