差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:2020.06.12-2020.06.18_周报 [2020/06/19 22:31]
chielo 创建
+++ 2020-2021:teams:intrepidsword:2020.06.12-2020.06.18_周报 [2020/07/05 21:19] (当前版本)
toxel revert
@@ 行 1: / 行 1: @@
 ===== 团队 =====
-.05.03 [[https://vjudge.net/contest/378303|2019 Multi-University Training Contest 2]] ''pro: 8/10/12'' ''rk: 11/874''
+.06.14 [[https://vjudge.net/contest/378303|2019 Multi-University Training Contest 2]] ''pro: 8/10/12'' ''rk: 11/874''
 ===== 个人 =====
@@ 行 17: / 行 17: @@
   * 6/18 - [[https://codeforces.com/contest/1368|Codeforces Global Round 8]]: ''pro: 4/4/9'' ''rk: 1108/12358''
+都是水题，一见难题场原形毕露。
 ===== 本周推荐 =====
@@ 行 25: / 行 26: @@
 ==== 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$。
+最大化贡献和。
+== 题解 ==
+<hidden>
+分职位 = 分 $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]]
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具