网络流代码只有普及难度,真正重要的地方在于建图——鲁迅
众所周知,网络流是刷蓝紫题的好工具;
本篇主要针对网络最大流与最小割;
[图论]网络流学习笔记-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 魔术球问题(可贪心)
暂无费用流和有界网络流