1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5 #define maxn 200 6 int a[maxn][maxn]; 7 int par[maxn]; 8 int n,len; 9 int num;10 struct node11 {12     int x;13     int y;14     int w;15 };16 node e[maxn * maxn / 2];17 int cmp(const node& a,const node &b)18 {19     return a.w < b.w;20 }21 int Find(int k)22 {23     if(par[k] == k)   return k;24     par[k] = Find(par[k]);25     return par[k];26 }27 void Merge(int x,int y)28 {29     int a = Find(x);30     int b = Find(y);31     if(a != b)32     {33         par[a] = b;34     }35 }36 37 void kruskal()38 {39 40     while(cin>>n)41     {42         for(int i = 0; i <= n+5; i++)43             par[i] = i;44         num = 0;45         len = 0;46         for(int i = 1; i <= n; i++)47             for(int j = 1; j <= n; j++)48                 cin>>a[i][j];49 50         for(int i = 1; i <= n; i++)51             for(int j = i + 1; j <= n; j++)52             {53                 e[num].x = i;54                 e[num].y = j;55                 e[num++].w = a[i][j];56             }57         sort(e,e+num,cmp);58         for(int i = 0; i < num; i++)59         {60             if(Find(e[i].x) != Find(e[i].y))61             {62                 Merge(e[i].x,e[i].y);63                 len += e[i].w;64             }65         }66         cout<<len<<endl;67     }68 69 }70 int main()71 {72     freopen("input.txt","r",stdin);73     kruskal();74 75     return 0;76 }