CVBB ACM Team

2020.06.14 2019 Multi-University Training Contest 2 pro: 8/10/12 rk: 11/874

• 6/12 - 牛客练习赛65: pro: 3/4/6 rk: 16/445
• 6/13 - Tokio Marine & Nichido Fire Insurance Programming Contest 2020: pro: 4/4/6 rk: 357/5966
• 6/13 - Codeforces Round #649 (Div. 2): pro: 4/4/5 rk: 222/9003
• 6/14 - AtCoder Beginner Contest 170: pro: 6/6/6 rk: 157/10433
• 6/18 - Codeforces Global Round 8: pro: 4/4/9 rk: 1108/12358

都是水题，一见难题场原形毕露。

直观理解就是进行多次增广之后，S 和 T 不再能通过有流量的边连通，即几个增广路上各取某条边，这些边切开了 S 到 T 的有向路（当然，每次增广需要跑满流量）。

更正式的证明一般将两个问题描述为线性规划，然后证明这对问题是对偶的。

当然，有时 S-T 最小割可能还需要拿到割集，或者 $S$ 集合和 $T$ 集合。 做法为，在跑完最大流的残余网络 (Residual network)上，从 S 找能访问到的点，这些点即为最小割的 $S$ 集合的一个解，其他点即 $T$ 集合，从 $S$ 集合单向到 $T$ 集合的边即为割集。

需要注意参与网络是包括反向边的，可参考一下 dingalapadum 的回答。

因 BZOJ 1001 狼抓兔子 (现在没了) 而闻名于世的定理，即平面图的 S-T 最小割权和，等于对偶图的最短路长度。

给定 $n$ 个点，$m$ 条边的无向图，求任意两点间的最小割权和大小。

？？？

实际上最小割权和的种类数并不多，比如找到了某两个点之间的最小割，很有可能对于另外某两个点可以用一样的割集得到最小割。

有时候可能这个模型藏得非常深，不细说了。

2019 HDU 多校 2 - H - Harmonious Army

最小割本身不难，跑个最大流而已，真正麻烦的是图的构造，甚至有时不一定看得出来是最小割或最大流的模型。

这个题目是要给士兵标记职位，“战士”或“法师”，每个战士只能有一个职位。 某两个战士如果均为战士则有个贡献 $a$，均为法师则有贡献 $c$，不一样则有贡献 $b = a/4+c/3$。 最大化贡献和。