网络流 / 费用流

## [大题单目录](https://www.luogu.com.cn/paste/7u925edr) [我爹 tarjen 的 flow 题单](https://vjudge.net/contest/601669#problem) 警告警告，此 tarjen 的题单难度极大 [CF1926G](https://www.luogu.com.cn/problem/CF1926G) 仅供建图参考 SP作为割的割集，连边就是树的连边 双向边割任意一次即可 [2024 CCPC 网络赛 G 题 ](https://codeforces.com/gym/105336) 最大流板子 [CF730I](https://codeforces.com/problemset/problem/730/I) 费用流板子 也可以反悔贪心模拟费用流 [2024IC网络赛第一场H](https://qoj.ac/contest/1794/problem/9315) 括号建模 [P1484](https://www.luogu.com.cn/problem/P1484) 模拟费用流 / 建图trick 仅作为思考方式 模拟费用流转WQS二分 + DP [QOJ7185](https://qoj.ac/problem/7185) 某一集合点少的情况下的暴力增广的模拟费用流板子 [2024百度之星决赛题目 ](https://www.matiji.net/exam/brushquestion/35/4498/F16DA07A4D99E21DFFEF46BD18FF68AD) 同上题 [黑暗爆炸](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-4977) 模拟费用流转反悔贪心 [AT_abc374_g](https://www.luogu.com.cn/problem/AT_abc374_g) 最少链覆盖转最大二分图匹配，缩点完传递闭包做二分图最大匹配 [CF2026E](https://codeforces.com/contest/2026/problem/E)最大闭合权子图问题 [CF1373F](https://codeforces.com/contest/1373/problem/F) 模拟最大流 转最小割后DP [arc125_e](https://atcoder.jp/contests/arc125/tasks/arc125_e) 模拟最大流 转最小割后 发现通过枚举A 二分BC情况即可 [P4001](https://www.luogu.com.cn/problem/P4001) 平面网格图转对偶图最小割跑最短路 [P2046](https://www.luogu.com.cn/problem/P2046) 同上 [P4897](https://www.luogu.com.cn/problem/P4897) 最小割树 [吉林 14th K](https://codeforces.com/gym/102800/attachments) 不保证满流 的 最小费用 [CF 739 E](https://codeforces.com/problemset/problem/739/E) 费用流 推式子 转化建图 [P3511](https://www.luogu.com.cn/problem/P3511) 二分欧拉回路转最大流 [CF1263F ](https://codeforces.com/contest/1263/problem/F) 原图转二分图式 考虑 最小割 [P2057](https://www.luogu.com.cn/problem/P2057) 考虑最小割 双向边朋友 因为让一个人不再要求另一个人的立场 割一条边 [P1251](https://www.luogu.com.cn/problem/P1251) // 将白天 晚上拆点拆开 // i+n 代表白天 i代表晚上 // 白天需要x块干净 晚上收到x块脏的 // 脏的毛巾 干净毛巾 都可以留到下一天 // 白天可以直接买不限量干净毛巾 // 当天晚上洗了脏的毛巾 多少天白天会收到干净的毛巾 两种洗法 [/P2754](https://www.luogu.com.cn/problem/P2754) 根据天数 分层图建图 [P2764](https://www.luogu.com.cn/problem/P2764) 最少链覆盖 拆入度出度点后 转最大二分图匹配 [P2765](https://www.luogu.com.cn/problem/P2765) 同上 [P2774](https://www.luogu.com.cn/problem/P2774) 行列二分图转最小割 [P3355](https://www.luogu.com.cn/problem/P3355) 同上 [P3356](https://www.luogu.com.cn/problem/P3356) 神经病输出方案遍历反向边残留网题目 喜欢我题解全都是链式前向星费用流吗 [P4009](https://www.luogu.com.cn/problem/P4009) 耗油为分层图 [P4012 ](https://www.luogu.com.cn/problem/P4012) 同时可以呆着 最简单的建图 最唐氏的输入调试 [P4013](https://www.luogu.com.cn/problem/P4013) 拆点集大成之题 [P4016](https://www.luogu.com.cn/problem/P4016) 类似上下界的 需要的进汇点 多余的作为源点 [P2936](https://www.luogu.com.cn/problem/P2936) 最大流板子 [P1345](https://www.luogu.com.cn/problem/P1345) 拆点 [P2045](https://www.luogu.com.cn/problem/P2045) 拆点 [P3410](https://www.luogu.com.cn/problem/P3410)最大闭合权子图问题 [P2805](https://www.luogu.com.cn/problem/P2805) 环上的不取 最大闭合权子图里面//被保护的连向保护的 保护的都死了左边都取 右部才能取到 [P2604](https://www.luogu.com.cn/problem/P2604) 带约束的 [CF1082G](https://www.luogu.com.cn/problem/CF1082G) 最大闭合权子图板子 [P5192](https://www.luogu.com.cn/problem/P5192) 有源汇上下界最大流 [P8215](https://www.luogu.com.cn/problem/P8215) 集合划分模型 好题 [P2053](https://www.luogu.com.cn/problem/P2053) 考虑拆等待时间考虑建图 [P2153](https://www.luogu.com.cn/problem/P2153) 同一个点只能走一次 拆点 [CF103E](https://www.luogu.com.cn/problem/CF103E) //左右都是k 取大数 最后都抵消 针对于最大闭合权子图这个模型来说 //数字取反 最大闭合权转最小 [P1231](https://www.luogu.com.cn/problem/P1231) 中间只能一个 拆点后跑最大流即可 [P1361](https://www.luogu.com.cn/problem/P1361)// 集合划分只能最小代价 全部减去最小 即为最后剩下最大贡献 // 因为有一起的附加 如果单个割掉 即整体被割 所以这里连INF 让其要么都被割 要么都不割 [P4313](https://www.luogu.com.cn/problem/P4313) 同上 [P6268](https://www.luogu.com.cn/problem/P6268) 二分图最大独立集 = 全集-最小点覆盖 = 全集-最小割 [P2055](https://www.luogu.com.cn/problem/P2055) 二分图式flow [P3701](https://www.luogu.com.cn/problem/P3701) 二分图式flow [P4304](https://www.luogu.com.cn/problem/P4304) 同平面网格图二分图式最小割 原理同舞会的二分图 [P7368](https://www.luogu.com.cn/problem/P7368) // 二分图最小点覆盖 转最小割 [CF1139E](https://www.luogu.com.cn/problem/CF1139E) 慢慢增加mex 看看能不能继续全部匹配上 有没有比前面匹配+1 根据加边来 [CF1684G](https://www.luogu.com.cn/problem/CF1684G) 通过3x，2x 与2y+x&&y%x==0构造 [CF1473F](https://codeforces.com/contest/1473/problem/F) 集合划分 类似最大闭合权子图 正负连源点汇点 约束条件为右边选了左边也必须选 所以中间约束连INF 这题建图要优化 考虑相同的时候 i i+1 i+2 相邻连一条边即可 [CF628F](https://www.luogu.com.cn/problem/CF628F) 唐逼flow