#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int Find(int s[],int num){
	for(;s[num]>=0;num=s[num]);
	return num;
}
void Union(int s[],int root1,int root2){
	s[root2]=root1;
}
int main(){
	int n=5;
	int map[5][5]={
 0,17,2,9,pow(2,31)-1,
 17,0,pow(2,31)-1,5,20,
 2,pow(2,31)-1,0,13,12,
 9,5,13,0,8,
 pow(2,31)-1,20,12,8,0
};
	int s[n];
	for(int i=0;i<n;i++){
		s[i]=-1;
	}
	int a[n-1],b[n-1];
	for(int i=0;i<n-1;i++){
		int min=pow(2,31)-1;
		for(int j=0;j<n-1;j++){
			for(int k=j+1;k<n;k++){
				if(map[j][k]<min&&Find(s,j)!=Find(s,k)){
					min=map[j][k];
					a[i]=j;
					b[i]=k;
				}
			}
		}
		int root1=Find(s,a[i]);
		int root2=Find(s,b[i]);
		Union(s,root1,root2);
	}
	int sum=0;
	printf("该最小生成树的路径有:\n");
	for(int i=0;i<n-1;i++){
		printf("V%d->V%d,长度为%d\n",a[i],b[i],map[a[i]][b[i]]);
		sum+=map[a[i]][b[i]];
	}
	printf("树的总权值为%d",sum);
	return 0;
}