网络流题集【转】

梦里梦外; 2022-06-09 11:16 95阅读 0赞

博客原文：[http://blog.csdn.net/shahdza/article/details/7779537][http_blog.csdn.net_shahdza_article_details_7779537]

最近搞网络流。。觉得这篇博客总结的题集感觉很有用，mark转载下来

【HDU】  
1532Drainage Ditches(入门) \[最大流\]  
3549Flow Problem(入门) \[最大流\]  
3572Task Schedule(基础) \[最大流\]任务分配,判断满流  
2732Leapin' Lizards(较难) \[最大流\]  
3338Kakuro Extension(较难，好题) \[最大流\]\[数和\]神奇最大流行进列出  
2883kebab(中等)\[最大流\]判断满流  
3605Escape(中等，好题)\[最大流\](可用多重匹配)  
4183Pahom on Water(基础) \[最大流\]来回走不重复点的网络流.  
4240 Route Redundancy(基础) \[最大流\]一条流最大的路径  
3081Marriage Match II(中等，好题) \[二分最大流\]+并查集  
3277Marriage Match III(中等，好题) \[二分最大流\]同上,多了拆点  
3416Marriage Match IV(中等，好题) \[最大流\]最短路+最大流  
2485Destroying the bus stations \[最大流\]最短路+最大流 **\[已验证最大流解法是错的\]**  
3468Treasure Hunting(中等) \[最大流\](二分匹配)+最短路  
3998Sequence(较难) \[DP+最大流\]最长上升子序列  
4309Seikimatsu Occult Tonneru(中等) \[最大流\]枚举状态+最大流  
3472HS BDC(难) \[混合欧拉\]  
\----------------------------------------------------------------------------------------------  
1533Going Home(入门题) \[费用流\]  
3488Tour(基础)\[费用流\]圈  
3435A new Graph Game(基础) \[费用流\]圈  
1853Cyclic Tour(基础) \[费用流\]圈  
2686Matrix(基础) \[费用流\]  
3376Matrix Again(基础) \[费用流\]  
3667Transportation(中等) \[费用流\]拆边  
3315My Brute(中等，好题)\[费用流\](可用KM)  
3395Special Fish(中等，好题) \[费用流\](可用KM匹配)  
2448Mining Station on the Sea(中等) \[费用流\](可用最短路+KM匹配)  
4067Random Maze(难) \[费用流\]

3947River Problem(难) \[费用流\]神奇费用流,流量不等式建图

4406 GPA \[好题\] \[官方题解为所谓的上下界费用流\]

4411 Arrest \[好题\] \[官方题解为所谓的上下界费用流\]

\---------------------------------------------------------------------------------------------  
3046Pleasant sheep and big big wolf(入门题) \[最小割\]  
1565方格取数(1)(基础) \[最小割\]黑白染色  
1569方格取数(2)(基础)\[最小割\]黑白染色  
3820Golden Eggs(较难，好题) \[最小割\]方格加强  
3491Thieves(中等) \[最小割\]最小点割集  
3657Game(中等) \[最小割\]最大点权独立集  
3313Key Vertex(中等) \[最小割\]  
3251Being a Hero(中等) \[最小割\]  
3452 Bonsai(基础) \[最小割\]一颗带边权的树,最小割求树根和叶子结点不连通  
3987 Harry Potter and the Forbidden Forest(较难，好题) \[最小割\]最小割的情况下,求最少需要割掉多少条边.  
2435There is a war(较难，好题) \[最小割\]打造无敌桥  
3917Road constructions(中等) \[最大权闭包\]最大获利  
3879Base Station(中等) \[最大权闭包\]最大获利  
3061Battle(中等) \[最大权闭包\]最大获利  
3996Gold Mine(中等) \[最大权闭包\]最大获利

4307Matrix(较难，好题) \[最小割\]\[项目分配问题\]

4265 Science! (较难)

4289 Control(中等) \[最小点权覆盖\]

4292 Food(基础) \[最大流\]

4322 Candy(难) \[好题\]\[最大流\]

========================================================================================================

**【POJ】**

**二分匹配能做的题目（拿来玩最大流的模板用吧。。。）：**

1087A Plug for UNIX \[最大流\](可用二分匹配)  
1274The Perfect Stall \[最大流\](可用二分匹配)  
1325Machine Schedule \[最大流\](可用二分匹配)  
1698Alice's Chance \[最大流\](可用二分匹配)  
2239Selecting Courses \[最大流\](可用二分匹配)  
2446Chessboard \[最大流\](可用二分匹配) 好题啊  
2536Gopher II \[最大流\](可用二分匹配)  
2771Guardian of Decency \[最大流\]二分匹配最大独立集  
3041 Asteroids \[最大流\](简单二分匹配)  
2584 T-Shirt Gumbo \[最大流\](多重匹配)  
3189 Steady Cow Assignment \[二分最大流\](多重匹配)

1149 PIGS(较难) \[最大流\] 绝对经典的构图题  
1273 Drainage Ditches(入门题) \[最大流\]  
1459 Power Network(入门题) \[最大流\]  
3281 Dining(入门题) \[最大流\]  
2112 Optimal Milking(中等) \[二分最大流\]  
2289 Jamie's Contact Groups(中等) \[二分最大流\]  
2391 Ombrophobic Bovines(中等) \[二分最大流\]  
2455 Secret Milking Machine(中等) \[二分最大流\]  
3228 Gold Transportation(中等) \[二分最大流\](并查集)  
2699 The Maximum Number of Strong Kings(较难) \[枚举人数 + 最大流\]  
3498March of the Penguins(中等) \[最大流\]枚举汇点,满足点容量限制的网络流  
1637 Sightseeing tour(难) \[混合欧拉\]  
\-------------------------------------------------------------------------------------------------------  
2135 Farm Tour(基础) \[费用流\] (来回最短路)  
2175Evacuation Plan(较难) \[费用流\] 消圈  
2195Going Home(入门题) \[费用流\]  
2516 Minimum Cost(中等) \[费用流\]  
3422 Kaka's Matrix Travels(中等) \[费用流\]拆点  
3680 Intervals(较难，好题) \[费用流\]经典,费用流+离散化  
3686The Windy's(难，好题) \[费用流\](KM匹配)

3762The Bonus Salary!(较难) \[费用流\]

\-------------------------------------------------------------------------------------------------------  
1815 Friendship(中等) \[最小割\]最小点割集  
1966 Cable TV Network(中等) \[最小割\]最小点割集  
2125 Destroying The Graph(难) \[最小割\]最小点权覆盖  
3084 Panic Room(中等，好题) \[最小割\]边连通度  
3204 Ikki's Story I - Road Reconstruction(中等) \[最小割\]求关键边  
3308 Paratroopers(较难) \[最小割\]乘积取对数,最小点权覆盖  
3436ACM Computer Factory \[最小割\]收集流,残留搜集找边  
3469 Dual Core CPU(中等) \[最小割\]项目分配问题  
3921Destroying the bus stations \[最小割\]点连通 \[删除!!!\]  
2987 Firing(较难，好题) \[最大权闭包\]  
3155 Hard Life(很挑战一题) \[最大密度子图\]  
=============================================================================================

**【其他OJ】**

LightOJ 上面已经有分类了,所以自己可以在上面找网络流的题目切吧。。。

zoj3348Schedule(基础，好题) \[最大流\]已经比了几场,还有几场没比.问DD能不能取得冠军  
zoj2760 How Many Shortest Path(基础) \[最大流\]不相交最短路径数  
zoj3460 Missile(中等) \[最大流\]按不同时间将每个点拆点,二分时间,判断是否是完美匹配.  
zoj3362 Beer Problem(中等) \[费用流\]最大费用流,每次增广.直到费用归本时,break;  
zoj2532 Internship(中等) \[最小割\]增加哪些边的流量,可以增大最大流.(求关键割边)  
ZOJ2587 Unique Attack(中等) \[最小割\](最小割的唯一性判定)  
ZOJ2539 Energy Minimization(较难，好题) \[最小割\]项目分配问题  
ZOJ2071 Technology Trader(较难，好题) \[最大权闭包\]输出选择方案  
ZOJ2332 Gems(中等) \[最大流\]  
  
SGU326 Perspective (构图题，类似于 WHU 1124)  
SGU438 The Glorious Karlutka River =) (按时间拆点)  
SGU242 Student's Morning (输出一组解)  
SGU185 Two shortest (Dijkstra 预处理，两次增广，必须用邻接阵实现，否则 MLE)  
  
HOJ2816 Power Line  
HOJ2634 How to earn more  
HOJ2811 Earthquake Damage (最小点割集)  
HOJ2715 Matrix3  
HOJ2739 The Chinese Postman Problem  
HOJ2543 Stone IV  
  
WHU1124 Football Coach (构图题)  
JOJ2453 Candy (构图题)  
TJU2944 Mussy Paper (最大权闭合子图)  
BUAA1032 Destroying a Painting  
BASHU2445(绝对经典的费用流) 餐巾问题  
  
SPOJ 839 Optimal Marks (将异或操作转化为对每一位求最小割)  
Spoj660：http://www.spoj.pl/problems/QUEST4/  
Spoj377：http://www.spoj.pl/problems/TAXI/  
  
\[UVA\]

753 , 820 , 10330 , 10735

11248 \[最大流\]先求起点到终点的最大流,然后在残留网络中,求起点到每个点的最大流,以及每个点到终点的最大流.然后枚举每条边增加容量能否满足题意.

\[TC\]:

Single Round Match 200 Round 1 – Division I, Level Three  
Single Round Match 236 Round 1 – Division I, Level Three  
Single Round Match 399 Round 1 – Division I, Level Three  
2003 TCO Semifinal Round 4 – Division I, Level Three  
2004 TCCC Championship Round – Division I, Level Three  
2005 TCO Sponsor Track Round 3 – Division I, Level One

\[RQNOJ\]

306 破坏石油运输系统问题  
338 \[NOI08\]志愿者招募  
529 \[NOI09\]植物大战僵尸  
556 \[NOI06\]最大获利

606 \[NOI2010\]海拔

=============================================================================================  
【上下界网络流】  
ZOJ 2314 可行流  
Zoj 3229 最大流  
zoj 1994 可行流

Pku 2396 可行流

poj 2594 最小流

Hdu3157 最小流  
Sgu176 最小流  
hust1342 最小流  
=============================================================================================  
【无向图最小割】  
hdu3691  
hdu3002  
poj2914  
poj1966  
zoj2753

=============================================================================================

[http_blog.csdn.net_shahdza_article_details_7779537]: http://blog.csdn.net/shahdza/article/details/7779537