网络流 练习记录
点击量：389
与LCT练习记录不同的是，这篇文章可能加入todo-list。
发现了宝贝
hihocoder里面的hiho一下在16年的时候总结了一些网络流的知识，以题目/模板的形式展现了出来，可以看看。
模板
洛谷 P3376 【模板】网络最大流
标准模板，可以检验出各种错误。
2018年8月之前都喜欢用EK写，直到看到了Dinic的板子——好短啊……
洛谷 P3381 【模板】最小费用最大流
也是费用流模板。写spfa时不开O2能接近1000ms。真理：人丑常数大
洛谷 P3386 【模板】二分图匹配
二分图匹配，可以直接用最大流做，只需要一个超级源点和超级汇点。超级源点到每个左侧点都连一条边；每个右侧点到超级汇点都连一条边。每条有向边容量为1。
这里不加特判
if(flow==0)
break;
会TLE，而模板3376就不会有这个问题。以后还是加上吧。
基础题
洛谷 P1231 教辅的组成
是一道“三分图”。实际上是把匹配转化为了三组元素，和二分图匹配的做法几乎一致，要读懂题目每个参量描述的是什么意思。
注意书要拆点，以保证所有的书只被包含在一套教辅里面。
网络流24题
进度从2019年1月10日开始统计。期望在省选前完成。
来源/题号/题目顺序：洛谷
- P1251 餐巾计划问题
- P2754 星际转移问题([CTSC1999]家园)
- P2756 飞行员配对方案问题
- 完成时间：2019/1/13
-
先在网上搜了一下网络流24题难度顺序，结果说最简单的就是这个。就是个二分图匹配……
- P2762 太空飞行计划问题
- P2763 试题库问题
- P2764 最小路径覆盖问题
- P2765 魔术球问题
- P2766 最长不下降子序列问题
- P2770 航空路线问题
-
- 完成时间：2019/1/20
-
根据题目要求，建立二分图，然后求出两部分的最大点权独立集。
- P3254 圆桌问题
- P3355 骑士共存问题
- P3356 火星探险问题
- P3357 最长k可重线段集问题
- P3358 最长k可重区间集问题
- P4009 汽车加油行驶问题
- P4011 孤岛营救问题
-
- 完成时间：2019/1/15
-
问题的关键在于如何让一个点的贡献只计算一次。
-
建两条边就可以了。
-
- 完成时间：2019/1/14
-
费用流板子，同下。
-
- 完成时间：2019/1/13
-
费用流模板。需要分别跑一次最小费用最大流和最大费用最大流。
-
其中最大费用最大流要用spfa找最长路。此时把原边权取反然后找最短路就可以了。
-
- 完成时间：2019/1/13
-
据说可以贪心做，有强数据版：洛谷 P2512 [HAOI2008]糖果传递
-
费用流做法：先求出均分后每个点有多少货物$ ave$，从$ S$向$ a_i<ave$的点连边，容量为$ ave-a_i$，表示需要输入这么多货物；从$ a_i>ave$的点向$ T$连边，容量为$ a_i-ave$。
-
于是这个题通过抽象理解的方法就能做出来了。（实际上连边相反更形象？）
有上下界的网络流
sgu 194 Reactor Cooling （无源汇）
(ZOJ也有这个题)
裸的上下界网络流了。
题解写在这里
poj 2396 Budget （有源汇）
这个题需要拆点。每个点多出来的那条边表示这个点的权值。
给每个源点和汇点连上相应流量的附加边，然后从$ S$到$ T$跑最大流就可以了。
洛谷 P4043 [AHOI2014/JSOI2014]支线剧情
这个题只有下界，但是需要计算费用。
一开始把题目看错了以为每个点都要经过一次，还变麻烦了
因为上下界网络流的特殊性，附加边已经帮原来的边跑掉了下界，因此计算答案时要额外加上每一条边的边权。
类似的题目（todo-list
每个点都要经过一次（这就是上面的题看错的解法）。
据说是最小流？也是DAG版的最小路径覆盖，每个边至少跑一次。
建立源点，连到所有入度为$ 0$的点；建立汇点，所有出度为$ 0(m=0)$的点连一条边到汇点。
然后针对这个有源汇的图（源汇无限流量）跑一下下界为$ 1$的可行流就可以了。
- bzoj 3698 XWW的难题 (权限题)
todo-list
- POJ 3308 Paratroopers
- 练习一圈后发现是简单题了……
-
- 神奇的建模
-
详见题解
-
-
拆成二分图，如果能全部匹配则有解，否则无解。注意每次会消掉一对点。
-
这题有毒吧横纵坐标倒过来输……
-
说点什么