网络瘤

骗分用的 这可能是这辈子倒数第二次写OI复习总结了.

网络流匹配二分图

做法很简单，假设二分图是A和B集合是二分图的集合，那么就从源点S连一条边向A集合，容量为1，然后AB之间的连边容量也是1，然后B连向汇点，跑最大流就是了。

最大流的模型

最小割

• [] 方格取数一个点选择了，那么它周围的点都不能被选择，非常像最小割模型，计算出所有点都选的代价，然后减去最小割，剩下的就是答案。考虑这样建图：把所有点黑白染色，然后源点向黑点连边，白点向汇点连边，容量点权，对于每一个黑点，都向它四边的白点连边，容量为INF。说白了就是看黑点点权大还是周围白点的点权大，扣去小的，最小割模型
• [] 太空飞行计划SPJ 也是一个总的和减去最小割的题如下图，又是一个花费和收益二选一的问题，显然就是最小割模型了。源点向实验连一条容量为实验收益的边，器材花费向汇点连边，然后跑一边最大流求最小割，于是就求出了最小舍弃量。

费用流

• [] 2629 「网络流 24 题」运输问题 费用流板题