Warning: session_start(): open(/tmp/sess_13988c694fa5e8e7161a052b87874d8b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14 [2020/10/22 09:24]
jjleo [题意]
2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14 [2020/10/22 09:35] (当前版本)
jjleo [题解]
行 92: 行 92:
   * 删除一条边。   * 删除一条边。
 ====题解==== ====题解====
 +考虑逆向过程,将删边改为加边,建出 Kruskal 重构树,非叶节点的权值代表子树中是第 $i$ 次删边操作前可以到达的连通块,之后倍增找祖先再套一个线段树维护 dfs 序,维护最小值和修改最小值即可。
 =====CF1408E===== =====CF1408E=====
 ====题意==== ====题意====
 +$m$ 个集合,里面放 $1$ 到 $n$ 的正整数。对于集合 $i$,如果里面有元素 $j$ 和 $k$,则在它们之间连一条颜色为 $i$ 的边。删除集合 $i$ 里面的数 $j$ 需要耗费 $a_i + b_j$ 的金钱,问使图不存在所有边颜色均不相同的环最少需要耗费多少钱。
 ====题解==== ====题解====
 +新建 $m$ 个点代表每个集合,将集合里每个元素像对于集合代表的点连边,可以发现这样构造后原图有彩虹环等价于新图有环,直接求最大生成树即可,然后用总权值减去生成树上的边权之和。
 =====CF1408G===== =====CF1408G=====
 ====题意==== ====题意====
2020-2021/teams/farmer_john/jjleo/2020.09.06-2020.10.14.1603329881.txt.gz · 最后更改: 2020/10/22 09:24 由 jjleo