暑期训练第二天，学习网络流……
包括SAP算法，SPFA费用流，zkw费用流等。
------算法模板-----
坑先放这，再填。
--------例题--------
学长说一道例题就蕴含一种思想。
例A.试题库问题
经典的网络流匹配问题。
建图：源点向每道题连流量为1的边，每道题向可属类型连流量为1的边，类型向汇点连流量为ki的边。
然后跑最大流，输出方案没啥好说的。
例B.危桥
考虑将往返看作走两次，然后强行跑最大流。
但是这样有个问题，就是万一a的流量流到b去了呢？
大家都说把b的起终点倒过来，我现在暂时还没有理解。
例C.奇怪的游戏
暂时还不会。
例D.飞行员配对方案问题
简单二分图匹配，不说了。
例E.紧急疏散EVACUATE
先搜出点与门间的距离。
然后二分逃离时间，按时间拆点，网络流check即可。
建图注意上个时间的点要向下个时间的点连INF边。
细节非常爆炸。
------比赛-------
地址:https://cn.vjudge.net/contest/235439
开始预判sigma ai==sigma bi
建图：拆点，汇点向各城市连拥有军队数的边，各城市向连接着的城市（包括自己）的子点连INF边，各城市子点向汇点连需要军队数的边。
跑最大流，然后输出方案。
二分小熊携带的重量，然后重建图，网络流check。
精度卡得厉害，WA了10次。
不会。
不会*2
附代码:以后有时间再放。
原文：https://www.cnblogs.com/JiuPleber/p/9231679.html