View Code of Problem 379

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 10050;
int m,n,k;
struct edge{ 
	int a,b; 
	int v; 
}s[maxn]; 
int pre[maxn];
bool cmp(edge a,edge b){return a.v < b.v;} 
int Find(int a){ 
	int root = a; 
	int tmp; 
	while(root != pre[root])root = pre[root]; 
	while(a != root){ 
		tmp = a; 
		a = pre[a]; 
		pre[tmp] = root; 
	} 
	return root; 
} 
void combine(int a,int b){ 
	int x = Find(a); 
	int y = Find(b); 
	if(x > y) 
		swap(x,y); 
	pre[y] = x; 
}
void kruskal(){ 
	int ans = 0;	
	for(int i=0;i<k;i++){ 
		if(Find(s[i].a)!=Find(s[i].b)){ 
 			combine(s[i].a,s[i].b); 
 			ans += s[i].v; 
 		} 
 	} 
 	printf("%d\n",ans);
}
int main(){
	while(~scanf("%d",&n))
	{
		
		k=0;
		for(int i=0;i<=n;i++)
		{
			pre[i]=i;
		}
		for(int i=0;i<n;i++)
		{	
			for(int j=0;j<n;j++){
				int a;
				scanf("%d",&a);
				s[k].a=i;
				s[k].b=j;
				s[k++].v=a;
			}
		}
		sort(s,s+k,cmp);
		kruskal();
	}
	return 0;
}