网络流
题单介绍
## Practice Mode
**网络流代码只有普及难度，真正重要的地方在于建图——鲁迅**
众所周知，网络流是刷蓝紫题的好工具；
本篇主要针对网络最大流与最小割；
[[图论]网络流学习笔记-Isap算法原理](https://www.luogu.com.cn/blog/lg-fengyueyk/post-tu-lun-wang-lao-liu-isap-suan-fa-xue-xi-bi-ji)；
[[图论]网络流练习笔记-Isap算法应用](https://www.luogu.com.cn/blog/lg-fengyueyk/post-tu-lun-wang-lao-zui-tai-liu-ying-yong)；
题目难度大致从前往后递增，个别除外。
该题单可用于不同类型网络流的普及和同类型网络流的复制刷分；
进阶版题单：[高级网络流](https://www.luogu.com.cn/training/147992)
### 类型
**朴素最大流：**
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 魔术球问题（可贪心）
暂无**费用流**和**有界网络流**