最小生成树---模板

最基础模板

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define V 110 //点的个数
#define E 5100  //边的个数

int parent[V];

int root(int p)
{
	if(parent[p]==-1) return p;
	else return parent[p]=root(parent[p]);
}
void merge(int a,int b)
{
	a=root(a);
	b=root(b);
	parent[a]=b;
}
struct node
{
	int a,b,len;
}p[E];

int cmp(node a,node b)
{
	return a.len<b.len;
}

int main()
{
	int i,j,k;
	int n,m,t;
	scanf("%d",&t);
	while(t--){
		memset(parent,-1,sizeof(parent));
		scanf("%d%d",&n,&m);
		int ans=0;
		while(m--){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			p[ans].a=a;
			p[ans].b=b;
			p[ans].len=c;
			ans++;
		}
		sort(p,p+ans,cmp);
		int sum=0;
		for(i=0;i<ans;i++)
		{
			if(root(p[i].a)!=root(p[i].b)){
				merge(p[i].a,p[i].b);
				sum+=p[i].len;
			}
		}
		printf("%d\n",sum);	
	}
	return 0;
}