网络流

题目汇总。

最小割

P2598 [ZJOI2009]狼和羊的故事

• 修建栏杆相当于是割断了狼和羊之间的联系方式，即割掉了一条边。在网格图中，建边的方式为由现在所在的格子向周围四个方向的格子连一条边。（理论上建立反向边比较赘余，但是因为在跑 Dinic 过程中涉及$i$（本条边）和$i \land 1$（反向边）的使用，所以建。)因此，在网络流中，要求割最少的边，使得网络不流通，为网络流最小割问题。需要用到的定理为：最小割$=$最大流。建图以后跑 Dinic 就好了。
• 最小割问题指的是，割去一些边之后，源点到汇点不再流通。这里要求一定要把狼和羊严格隔开，距离无法隔开他们，也就是说即使他们隔着很多个$0$的格子，也是可以互相到达的！这就不满足题目条件了。

P2774 方格取数问题

• 奇数点放一边，偶数点放一边，建立二分图。建完边后，考虑继续连边，将所有可能产生影响的边连接在一起，这里只要把黑点连向白点就可以了。因为最开始在构建这个网络流的时候，方向已经定为$S$->黑->白->$T$了。
• 如果只看$j$的奇偶性的话会出问题，因为就相当于不会影响上下的格子。

CF1198E Rectangle Painting 2

• 把一个$h*w$的矩形区域覆盖的代价是$\min(h,w)$，因此选择一个大小为$1*k$或$k*1$的区间显然非常优秀。如果多个区间可以合并的话，$n*k$显然代价等于$n* \min(1,k)$或$k* \min(n,1)$，并且数据中区间所占行数和列数离散化后又不是很多，因此可以这么做！
• 关于离散化
  1）$uxn，uyn$保存的是离散化后数组总个数，不是最大值；
  2）通过画图可以发现，$ux[i+1]-ux[i]$确实包含了所有的矩形，但是有可能把把两个矩形切成三个矩形；
  3）至于为什么要变作闭右开区间，因为这样确实可以很好的覆盖所有的数，是一种技巧。
• 关于最小覆盖
  在这个题目中，最小覆盖=最小割=最大流。

最小费用最大流

P3159 [CQOI2012]交换棋子

• 题目涉及黑白棋子和两种状态，均考虑显然比较繁杂。暂且先不管白棋子和不变色的黑棋子，将所有初始状态就是黑棋子的点与源点相连，最终状态是黑棋子的点与汇点相连。因为黑棋子的交换可以看作移动，显然只有端点只交换了一次其他中间点交换了两次因此建边时流量应$/2$。
• 建边方式如下：
  1）连源汇，流量$1$，费用$0$，表示有待匹配；
  2）中间点，初始状态与最终状态相连，流量为交换次数$/2$，费用为$0$；
  3）初始状态与最终状态不同，且可交换次数为奇数的黑棋，单独向最终状态连一条边，流量$1$，费用$0$；
  4）处理格点，向八个方向连边，流量$INF$，费用$1$，即交换需要付出的代价。
• 跑模板即可。

P1251 餐巾计划问题

• 题目涉及多种增加当天可利用的餐巾数量的可能，需要一步一步分清况讨论。
• 建边方式：
  1）源点向每一天早上连入一条流量为 INF ，费用为$p$的边：可以购买新的餐巾；
  2）源点向每一天晚上连入一条流量为$a_i$，费用为$0$的边：从起点获得脏餐巾，即今天用过了的餐巾；
  3）每一天早上向汇点连入一条流量为$a_i$，费用为$0$的边：向汇点提供干净餐巾，如果流满了，那么$i$号节点的餐巾显然是够用的（前几天剩得够多，能够支持今天的消耗）；
  4）每一天向快洗$m$天、慢洗$n$天后连流量为 INF ，费用为$f$或$ss$的边：快洗/慢洗
• 跑最小费用最大流即可。

P3980 [NOI2008] 志愿者招募

• 明显的费用流，注意连边应该要往后多连一个点。
• 建边方式：
  1）第一天连源点，第$n+1$天连汇点
  2）每一天向后连一天
  3）特殊时间段起点连向终点$+1$
• 最小费用最大流。