===== 团队 ===== 2020.06.14 [[https://vjudge.net/contest/378303|2019 Multi-University Training Contest 2]] ''pro: 8/10/12'' ''rk: 11/874'' ===== 个人 ===== ==== zzh ==== ==== pmxm ==== ==== jsh ==== * 6/12 - [[https://ac.nowcoder.com/acm/contest/5961|牛客练习赛65]]: ''pro: 3/4/6'' ''rk: 16/445'' * 6/13 - [[https://atcoder.jp/contests/tokiomarine2020|Tokio Marine & Nichido Fire Insurance Programming Contest 2020]]: ''pro: 4/4/6'' ''rk: 357/5966'' * 6/13 - [[https://codeforces.com/contest/1364|Codeforces Round #649 (Div. 2)]]: ''pro: 4/4/5'' ''rk: 222/9003'' * 6/14 - [[https://atcoder.jp/contests/abc170|AtCoder Beginner Contest 170]]: ''pro: 6/6/6'' ''rk: 157/10433'' * 6/18 - [[https://codeforces.com/contest/1368|Codeforces Global Round 8]]: ''pro: 4/4/9'' ''rk: 1108/12358'' 都是水题，一见难题场原形毕露。 ===== 本周推荐 ===== ==== zzh ==== ==== pmxm ==== ==== jsh ==== === 最大流 <=> S-T 最小割 === 直观理解就是进行多次增广之后，S 和 T 不再能通过有流量的边连通，即几个增广路上各取某条边，这些边切开了 S 到 T 的有向路（当然，每次增广需要跑满流量）。 更正式的证明一般将两个问题描述为线性规划，然后证明这对问题是对偶的。 === 最小割割集 === 当然，有时 S-T 最小割可能还需要拿到割集，或者 $S$ 集合和 $T$ 集合。 做法为，在跑完最大流的**残余网络 (Residual network)**上，从 S 找能访问到的点，这些点即为最小割的 $S$ 集合的一个解，其他点即 $T$ 集合，从 $S$ 集合单向到 $T$ 集合的边即为割集。 需要注意参与网络是包括反向边的，可参考一下 [[https://stackoverflow.com/a/21219223/4287864|dingalapadum 的回答]]。 === 平面图上的最小割 === 因 BZOJ 1001 狼抓兔子 (现在没了) 而闻名于世的定理，即平面图的 S-T 最小割权和，等于对偶图的最短路长度。 === 最小割树 (Gomory-Hu Tree) （！） === 给定 $n$ 个点，$m$ 条边的无向图，求**任意两点间**的最小割权和大小。 ？？？ 实际上最小割权和的种类数并不多，比如找到了某两个点之间的最小割，很有可能对于另外某两个点可以用一样的割集得到最小割。 有时候可能这个模型藏得非常深，不细说了。 === 最小割例题 === [[http://acm.hdu.edu.cn/showproblem.php?pid=6598|2019 HDU 多校 2 - H - Harmonious Army]] 最小割本身不难，跑个最大流而已，真正麻烦的是图的构造，甚至有时不一定看得出来是最小割或最大流的模型。 == 题意 == 这个题目是要给士兵标记职位，“战士”或“法师”，每个战士只能有一个职位。 某两个战士如果均为战士则有个贡献 $a$，均为法师则有贡献 $c$，不一样则有贡献 $b = a/4+c/3$。 最大化贡献和。 == 题解 == 分职位 = 分 $S$ 集合和 $T$ 集合。 题目要最大化，想用最小割就得倒着减。 那我们先把 $a + c$ 加到答案里，让最小割自己来减 $a$ 或 $c$ 或 $a+c-b = 3a/4+2c/3$。 减 $a$ 减 $c$ 好说，即两个点分在了同一个集合，那么我们把这两个点和 $T$、$S$ 分别连接 $c/2$, $a/2$ 流量的边即可（有向边）。 减 $a+c-b$ 说明两个点分在了不同的集合，已经割掉了 $a/2+c/2$ 了，那么我们需要这两个点之间连接一条 $a/4+c/6$ 流量的边（无向边，即两个有向边）。 实现上上述的值都乘个 $2$ 才能让边权都为整数，最后答案除以 $2$ 即可。 ISAP 实现：[[https://vjudge.net/solution/26000797|#26000797]]