#P9739. 瘟疫公司

    ID: 6364 传统题 2000ms 256MiB 尝试: 40 已通过: 11 难度: 7 上传者: 标签>CF2300提高+/省选-子集 DPSOS DPKruskal普通并查集

瘟疫公司

题目描述

给定一张由 nn 个城市和 mm 条带权道路组成的连通无向图。对于一个非空的城市集合 SS,取所有两端都在 SS 中的道路,得到 SS 的诱导子图。若该子图连通,定义 w(S)w(S) 为其最小生成树的边权和与最大生成树的边权和的按位异或。

开始时任选一个城市感染。若当前感染集合为 SS,可以将其扩张为任意严格包含 SS 且诱导子图连通的城市集合 TT。这一步的 DNA 消耗为 (∣T∣−∣S∣) w(T)(|T|-|S|)\,w(T)。

求将所有城市感染所需的最小 DNA 消耗。

输入格式

第一行两个正整数 n,mn,m。

接下来 mm 行,每行三个正整数 u,v,wu,v,w,表示连接城市 u,vu,v 的一条道路,边权为 ww。

输出格式

输出一行一个整数,表示最小 DNA 消耗。

样例

3 3
1 2 1
1 3 2
2 3 3
6

原题另有下发样例,见 plague2.in 和 plague2.ans。

数据范围

对于全部数据,1≤n≤201\le n\le20,1≤m≤1001\le m\le100,1≤w≤100001\le w\le10000,保证原图连通。

原题测试点 nn 上限 mm 上限
1–4 3 10
5–6 4
7–8 5
9–12 10 100
13–16 16
17–20 20

原 PDF 题面