P30053

唯一最小生成树

难度 6 级 最小生成树 图论
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给出一个有权值的无向图 G,请你判断 G 的最小生成树是否唯一。如果不唯一,输出 No,如果唯一,输出最小生成树的边权之和。

输入

第一行:一个数 T,表示测试组数(1 \le T \le 20)。

后面每一个测试用例:

第一行:2 个数 n, m,中间用空格分割,对应点的数量和边的数量(1 \le n \le 100,1 \le m \le \frac{n(n-1)}{2})。

后面 m 行,每行 3 个数:u, v, w,表示点 u 和点 v 之间有边,权值为 w(1 \le u, v \le n,1 \le w_i \le 10000)。

输出

如果不唯一,输出 No;如果唯一,输出最小生成树的边权之和。

样例

样例 1
输入
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
输出
3
No

提示

样例解释

  • 第一个测试用例:最小生成树唯一,边权和为 1 + 2 = 3。
  • 第二个测试用例:图是一个环,所有边权均为 2,有多个最小生成树(任选三条边),不唯一,输出 No。
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交