Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph has a minimum spanning forest.
Now given some connected, undirected graph, output the minimum spanning tree weight.
The format of input is same as problem C, in the form of matrix, but the maximum vertex number is 1000.
For each test case, output the minimum spanning tree weight.
2 0 1 1 0 3 0 1 -1 1 0 1 -1 1 0
1 2
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|