两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
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===== | ||
====题意==== | ====题意==== |