CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 团队 =====

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$。
最大化贡献和。

== 题解 ==

<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

用户工具

站点工具

页面工具
