【W的AC计划 - 第九期】网络流
题单
P1344：最小割、数学技巧
由两问构成，第一问直接运行最小割即可，第二问比较困难，容易想到建议另一个边权均为 \(1\) 的网络然后再跑一遍最小割，然而这样是错误的：新图的答案并不对应给定图的最小割，hack数据见此。
所以这里采用一个智慧的数学技巧：将给定边权扩大后用末尾位记录第二问的答案，能同时跑出两个问的答案，分离后输出即可。
P2598：最小割、矩阵
比较偏基础题，我们能够发现，由于值为 \(0\) 的格子不与源汇相连接，故不影响答案，所以我们可以暴力连出所有的边，再将源点与羊连接、狼与汇点连接，直接用最小割来解决问题，注意这样暴力建图导致答案是翻倍的，所以要除以 \(2\) 。
还有一个略微优化的技巧，即我们发现，羊与羊、狼与狼之间一定不会有栅栏，所以可以特判、跳过这样的情况，但是空地和空地间是有可能有栅栏的，所以不能跳过（因为这个WA了两发），这样建图答案就不用除以 \(2\) 了。加上这个优化之后空间能小一半，速度也可以快一些。
P3931：最小割、图论-树形遍历
有其他做法。按照题意模拟建图后跑最小割模板即可，注意给定的树是无向树，阴间出题人没有声明这一点，我直接WA……
P1345：最小割、图论技巧-拆点
这道题的难点在于要删除的是点而不是边，我们常规意义上的网络流都是对边进行操作的，所以我们这里使用“拆点”的图论技巧，将一个点拆成两个，他们中间连的边即为需要被计算的那条边，随后便是最小割。
需要注意的是，源汇点拆点后连边的边权应当为 INF ，因为源汇不能被删除，随后，在严格意义上我们需要将汇点修改为 \(t+n\) ，然而因为边权无穷大，所以不修改也不影响答案；当然，还有一种做法是连边权为 \(1\) 的边后将源点修改为 \(s+n\) 、汇点不变。
1082G：最大权闭合子图
模板。