The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm 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 farm i to itself is not interesting for this problem.

For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

28

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn=10005;
 8 
 9 struct edge{
10     int u,v,cost;
11     bool operator<(const edge& i)const{
12         return cost<i.cost;
13     }
14 }es[maxn];
15 
16 int n,cnt;
17 int F[maxn],map[101][101];
18 
19 int Find(int a){
20     if(a!=F[a]) F[a]=Find(F[a]);
21     return F[a];
22 }
23 
24 bool unite(int a,int b){
25     int x=Find(a),y=Find(b);
26     if(x!=y) { F[x]=y; return true; }
27     else return false;
28 } 
29 
30 int Kruskal(){
31     sort(es,es+cnt);
32     int ans=0;
33     for(int i=0;i<cnt;i++){
34         edge e=es[i];
35         if(unite(e.u,e.v)) ans=ans+e.cost;
36     }
37     return ans;
38 }
39 
40 int main()
41 {    while(cin>>n){
42         cnt=0;
43         for(int i=0;i<n;i++){ 
44             for(int j=0;j<n;j++){
45                 scanf("%d",&map[i][j]);
46                 es[cnt].u=i;
47                 es[cnt].v=j;
48                 es[cnt].cost=map[i][j];
49                 cnt++;
50             }
51         }
52         for(int i=0;i<n;i++) F[i]=i;
53         cout<<Kruskal()<<endl;
54     }
55     return 0;
56 }