【网络流&二分图模型套路总结】
- 棋盘选数：可以看做行，列进行二分图匹配。
例题：
[SCOI2015]小凸玩矩阵 - 分配问题，每个点初始有一些物品，通过一些“规则”可以移到别的点上，询问最终每个点的物品数是否满足给定的条件。建模时把物品当做流，把每个点拆成初始点和最终点。有可能询问时间，可以把时间二分，则“规则”可以通过最短路预处理。
例题：
奶牛隐藏
CF852D Exploration plan
CF546E Soldier and Traveling
CF546E Soldier and Traveling
这道题的不同之处是要构造方案，可以通过查看反向边来输出方案。 - 最小割
有向图有源汇最小割=有向图有源汇最大流
无向图有源汇最小割=无向图有源汇最大流
证明：可以直接将无向图的每条边当成两条相反的有向边，变成有向图，那么就变成了求这个有向图的最小割，而且可以发现无向图的一条边不可能被当成两条有向边边删两次从而使边权多加一次。原因是，两条有向边都被删一定满足这两条边都流满，而这与不经过这两条边无异。
P4662 [BalticOI 2008]黑手党