Minimum spanning trees P12887
Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. On a weighted graph, the weight of a spanning tree is the sum of the weights of its edges. A minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.
Input
Input consists of different weighted, connected, undirected graphs. For each graph, the following integers are given: First, n ≥ 1 represents the number of vertices on the graph. Then, m represents the number of edges on the graph. Finally, a set of m weighted edges u,v,w is given by specifying its two end points u and v and its weight w ≥ 1. Vertices are numbered starting from 1. There are no edges connecting a vertex to itself, but there may be more than two edges connecting the same pair of vertices. Every given graph is connected. All weights are strictly positive integers.
Output
For every graph in the input, write the weight of its minimum spanning tree.
Input
5 6
1 2 3
1 3 8
2 4 5
3 4 2
3 5 4
4 5 6
3 3
2 1 20
3 1 20
2 3 100
Output
14 40
- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++ Python Python
- User solutions
- C++ Python