#P9739. 瘟疫公司
瘟疫公司
题目描述
给定一张由 个城市和 条带权道路组成的连通无向图。对于一个非空的城市集合 ,取所有两端都在 中的道路,得到 的诱导子图。若该子图连通,定义 为其最小生成树的边权和与最大生成树的边权和的按位异或。
开始时任选一个城市感染。若当前感染集合为 ,可以将其扩张为任意严格包含 且诱导子图连通的城市集合 。这一步的 DNA 消耗为 。
求将所有城市感染所需的最小 DNA 消耗。
输入格式
第一行两个正整数 。
接下来 行,每行三个正整数 ,表示连接城市 的一条道路,边权为 。
输出格式
输出一行一个整数,表示最小 DNA 消耗。
样例
3 3
1 2 1
1 3 2
2 3 3
6
原题另有下发样例,见 plague2.in 和 plague2.ans。
数据范围
对于全部数据,,,,保证原图连通。
| 原题测试点 | 上限 | 上限 |
|---|---|---|
| 1–4 | 3 | 10 |
| 5–6 | 4 | |
| 7–8 | 5 | |
| 9–12 | 10 | 100 |
| 13–16 | 16 | |
| 17–20 | 20 |