-
T303177伊基的故事 I - 道路重建
这题就是求增加一条边的容量，能改变最大流，求边的个数。
我们求完网络流之后，只需查看有多少边所连接的点在残量网络上分别与 S 和 T 联通即可。
-
T303637秘密挤奶机
首先答案具有决策单调性，所以我们二分答案，然后再用可以走的边构成网络流。
那么双向边怎么办呢？只需将每条边的反向边的初始容量设为 1 即可。
-
P2754 [CTSC1999] 家园 / 星际转移问题
不难发现答案不会超过 nmk，所以按时间拆点后枚举时间连边建图即可。
-
UVA12125 March of the Penguins
这题由于每块冰有一个跳的次数的限制，所以将每块冰拆成两个点，分别为入点出点，之间连一个边权为能承受的数量，枚举 T，看一下能不能跑满流即可。
-
T303638 猪
由于可以交换猪，所以对于一个顾客 i，可以转化为他新开了一个养猪场，把他能打开的猪圈的猪都拿来了，卖了 \(b_{i}\) 个，然后也可以让别人拿， 于是有以下建图：
将 S 向每一个猪圈 i 连一个容量为猪的个数的边，对于一个顾客 j，枚举所有的 \(K_{j, k}\)，如果这个猪圈被打开过，则向最后一个打开它的人连 INF 的边，否则向猪圈连 INF 的边，最后每个顾客向 T 连 B 的边。
by zpl
标签：题目,最大,建图,这题,枚举,猪圈,即可,INF From： https://www.cnblogs.com/classblog/p/18261601