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:33] jjleo [题意] |
2020-2021:teams:farmer_john:jjleo:2020.09.06-2020.10.14 [2020/10/22 09:35] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 97: | 行 97: | ||
| $m$ 个集合，里面放 $1$ 到 $n$ 的正整数。对于集合 $i$，如果里面有元素 $j$ 和 $k$，则在它们之间连一条颜色为 $i$ 的边。删除集合 $i$ 里面的数 $j$ 需要耗费 $a_i + b_j$ 的金钱，问使图不存在所有边颜色均不相同的环最少需要耗费多少钱。 | $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.1603330403.txt.gz · 最后更改: 2020/10/22 09:33 由 jjleo
