2020-2021:teams:intrepidsword:2020.06.12-2020.06.18_周报
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.06.12-2020.06.18_周报 [2020/06/19 23:22] chielo [jsh] |
2020-2021:teams:intrepidsword:2020.06.12-2020.06.18_周报 [2020/07/05 21:19] (当前版本) toxel revert |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ===== 团队 ===== | ===== 团队 ===== | ||
| - | 2020.05.03 [[https://vjudge.net/contest/378303|2019 Multi-University Training Contest 2]] ''pro: 8/10/12'' ''rk: 11/874'' | + | 2020.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'' | * 6/18 - [[https://codeforces.com/contest/1368|Codeforces Global Round 8]]: ''pro: 4/4/9'' ''rk: 1108/12358'' | ||
| + | 都是水题，一见难题场原形毕露。 | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| 行 32: | 行 33: | ||
| - | == 割集 == | + | === 最小割割集 === |
| 当然，有时 S-T 最小割可能还需要拿到割集，或者 $S$ 集合和 $T$ 集合。 | 当然，有时 S-T 最小割可能还需要拿到割集，或者 $S$ 集合和 $T$ 集合。 | ||
| 行 40: | 行 41: | ||
| - | == 平面图 == | + | === 平面图上的最小割 === |
| 因 BZOJ 1001 狼抓兔子 (现在没了) 而闻名于世的定理，即平面图的 S-T 最小割权和，等于对偶图的最短路长度。 | 因 BZOJ 1001 狼抓兔子 (现在没了) 而闻名于世的定理，即平面图的 S-T 最小割权和，等于对偶图的最短路长度。 | ||
| - | == 最小割树 (Gomory-Hu Tree) （！） == | + | === 最小割树 (Gomory-Hu Tree) （！） === |
| 给定 $n$ 个点，$m$ 条边的无向图，求**任意两点间**的最小割权和大小。 | 给定 $n$ 个点，$m$ 条边的无向图，求**任意两点间**的最小割权和大小。 | ||
| 行 56: | 行 57: | ||
| - | == 最小割例题 == | + | === 最小割例题 === |
| [[http://acm.hdu.edu.cn/showproblem.php?pid=6598|2019 HDU 多校 2 - H - Harmonious Army]] | [[http://acm.hdu.edu.cn/showproblem.php?pid=6598|2019 HDU 多校 2 - H - Harmonious Army]] | ||
| 最小割本身不难，跑个最大流而已，真正麻烦的是图的构造，甚至有时不一定看得出来是最小割或最大流的模型。 | 最小割本身不难，跑个最大流而已，真正麻烦的是图的构造，甚至有时不一定看得出来是最小割或最大流的模型。 | ||
| + | |||
| + | == 题意 == | ||
| 这个题目是要给士兵标记职位，“战士”或“法师”，每个战士只能有一个职位。 | 这个题目是要给士兵标记职位，“战士”或“法师”，每个战士只能有一个职位。 | ||
| 行 66: | 行 69: | ||
| 最大化贡献和。 | 最大化贡献和。 | ||
| + | == 题解 == | ||
| + | |||
| + | <hidden> | ||
| 分职位 = 分 $S$ 集合和 $T$ 集合。 | 分职位 = 分 $S$ 集合和 $T$ 集合。 | ||
| 行 79: | 行 85: | ||
| ISAP 实现：[[https://vjudge.net/solution/26000797|#26000797]] | ISAP 实现：[[https://vjudge.net/solution/26000797|#26000797]] | ||
| + | </hidden> | ||
2020-2021/teams/intrepidsword/2020.06.12-2020.06.18_周报.1592580139.txt.gz · 最后更改: 2020/06/19 23:22 由 chielo
