-->
当前位置:首页 > 题库

PROGRAMMING:Uniqueness of minimum spanning tree

Luz5年前 (2021-05-10)题库482
Given a weighted undirected graph, if it is a connected graph, there is at least one minimum spanning tree, sometimes the minimum spanning tree is not unique. This problem requires you to calculate the total weight of the minimum spanning tree, and judge whether it is unique.
###Input format:
First of all, the first line gives two integers: vertex number $$n $$($$Le 500 $$) and edge number $$M $$. Next, $$M $$lines, each line gives two endpoints and weights of an edge in the format of "vertex 1 Vertex 2 weight", where the vertices are numbered from 1 to $$n $, and the weight is a positive integer. The topic guarantees that the total weight of the minimum spanning tree will not exceed $$2 ^ {30} $$.
###Output format:
If there is a minimum spanning tree, first output its total weight in the first row, and output "yes" in the second row. If the tree is unique, otherwise output "no". If the tree does not exist, the first row outputs "no MST", and the second row outputs the number of connected sets of the graph.
###Input sample 1:
```in
5 7
1 2 6
5 1 1
2 3 4
3 4 3
4 1 7
2 4 2
4 5 5
```
###Output sample 1:
```out
eleven
Yes
```
###Input example 2:
```in
4 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3
```
###Output example 2:
```out
four
No
```
###Input sample 3:
```in
5 5
1 2 1
2 3 1
3 4 2
4 1 2
3 1 3
```
###Output example 3:
```out
No MST
two
```







answer:If there is no answer, please comment