문제1100--Finding a MST

1100: Finding a MST

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 412  통과: 102
[제출] [채점기록] [묻고답하기]

문제 설명

Given a graph, you must find a minimum spanning tree for the graph.

입력 설명

The input includes several cases. For each case, the first line contains the number of vertex, $N (3 \leq N \leq 100)$. The following lines contain the $N$ x $N$ conectivity matrix, where each element shows the weight fo edge from on vertex to another. Logically, they are $N$ lines of $N$ space-separated integers. Physically, they are limited in length to $80$ characters, so some lines continue onto others. Of course, the diagonal will be $0$, since the distance from vertex $i$ to itself is not interesting for this problem.

출력 설명

For each test case, print sum of weights for MST.

입력 예시 Copy

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
2
0 1
1 0

출력 예시 Copy

28
1

출처/분류