网络流

Practice Mode

网络流代码只有普及难度,真正重要的地方在于建图——鲁迅

众所周知,网络流是刷蓝紫题的好工具;

本篇主要针对网络最大流与最小割;

[图论]网络流学习笔记-Isap算法原理;

[图论]网络流练习笔记-Isap算法应用;

题目难度大致从前往后递增,个别除外。

该题单可用于不同类型网络流的普及和同类型网络流的复制刷分;

进阶版题单:高级网络流

类型

朴素最大流:

P3376   【模板】网络最大流
P2740   [USACO4.2]草地排水Drainage Ditches
P3163   [CQOI2014] 危桥

二分图最大流:

P2756   飞行员配对方案问题
P3701   主主树
P3254   圆桌问题
P2763   试题库问题

三分图最大流:

P1402   酒店之王
P1231   教辅的组成
P2891   [USACO07OPEN]Dining G

多层图最大流:

P2754   [CTSC1999]家园 / 星际转移问题

朴素最小割:

P2057   [SHOI2007]善意的投票 / [JLOI2010]冠军调查
P4001   [ICPC-Beijing 2006]狼抓兔子
P2598   [ZJOI2009]狼和羊的故事

流点与割点:

P1345   [USACO5.4]奶牛的电信Telecowmunication
P2944   [USACO09MAR]Earthquake Damage 2 G
P2472   [SCOI2007]蜥蜴
P4311   士兵占领

二分图最小割:

P2774   方格取数问题
P3355   骑士共存问题
P5030   长脖子鹿放置
P4304   [TJOI2013]攻击装置
P4474   王者之剑

合点最小割:

P1646   [国家集训队]happiness
P1361   小M的作物
P4313   文理分科

最小路径覆盖:

P2764   最小路径覆盖问题
P2172   [国家集训队]部落战争

最大权闭合子图:

P2762   太空飞行计划问题
CF1082G Petya and Graph
P4174   [NOI2006] 最大获利
P2805   [NOI2009] 植物大战僵尸

生成树 + 网络流:

P5039   [SHOI2010]最小生成树
P5934   [清华集训2012]最小生成树

二分 + 网络流:

P3153   [CQOI2009]跳舞
P3305   [SDOI2013]费用流
P3324   [SDOI2015]星际战争
P5038   [SCOI2012]奇怪的游戏

-DP- + 网络流:

P2766   最长不下降子序列问题
P3171   [CQOI2015]网络吞吐量

其它 + 网络流:

P2765   魔术球问题(可贪心)

暂无费用流有界网络流


  1. P3376 - 【模板】网络最大流
  2. P2756 - 飞行员配对方案问题
  3. P3701 - 主主树
  4. P2057 - [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查
  5. P1345 - [USACO5.4] 奶牛的电信 Telecowmunication
  6. P2740 - [USACO4.2] 草地排水 Drainage Ditches
  7. P2944 - [USACO09MAR] Earthquake Damage 2 G
  8. P4001 - [ICPC 2006 Beijing R] 狼抓兔子
  9. P2598 - [ZJOI2009] 狼和羊的故事
  10. P2472 - [SCOI2007] 蜥蜴
  11. P2763 - 试题库问题
  12. P3254 - 圆桌问题
  13. P1402 - 酒店之王
  14. P1231 - 教辅的组成
  15. P2765 - 魔术球问题
  16. P4474 - 王者之剑
  17. P2774 - 方格取数问题
  18. P3355 - 骑士共存问题
  19. P5030 - 长脖子鹿放置
  20. P4304 - [TJOI2013] 攻击装置
  21. P2764 - 最小路径覆盖问题
  22. P2172 - [国家集训队] 部落战争
  23. P2762 - 太空飞行计划问题
  24. P4174 - [NOI2006] 最大获利
  25. CF1082G - Petya and Graph
  26. P5039 - [SHOI2010] 最小生成树
  27. P5934 - [清华集训 2012] 最小生成树
  28. P2766 - 最长不下降子序列问题
  29. P1646 - [国家集训队] happiness
  30. P1361 - 小M的作物
  31. P4313 - 文理分科
  32. P4311 - 士兵占领
  33. P2891 - [USACO07OPEN] Dining G
  34. P3171 - [CQOI2015] 网络吞吐量
  35. P3163 - [CQOI2014] 危桥
  36. P3153 - [CQOI2009] 跳舞
  37. P3305 - [SDOI2013] 费用流
  38. P3324 - [SDOI2015] 星际战争
  39. P2805 - [NOI2009] 植物大战僵尸
  40. P2754 - [CTSC1999] 家园 / 星际转移问题
  41. P5038 - [SCOI2012] 奇怪的游戏