//Kruskal 算法的实现#include <iostream>#include <string>#include <iomanip>#include <cctype>#include <cstdio>#include <cstring>#include <algorithm>using namespace std; struct node{	int u;	int v;	int w;};int father[101];int son[101];int cmp(node a, node b){    return a.w<b.w;}int find(int x){	return x==father[x]? x : find(father[x]);}bool join(int x, int y) //加入者两个点连成的边 会怎样？{    int xx=find(x);	int yy=find(y);	if(xx==yy)		return false; //加入此边 将构成环路  返回false	else if( son[xx]>=son[yy] )	{        father[yy] = xx;		son[xx] = son[xx]+son[yy];	}	else	{		father[xx]=yy;		son[yy] = son[yy]+son[xx];	}    return true;}int main(){	int n, m;	int i, j;    int cnt;	int sum;    node edge[1000];	while(cin>>n>>m)	{		if(m==0)		{			cout<<"0\n";			continue;		}		for(i=0; i<m; i++)		{			cin>>edge[i].u>>edge[i].v>>edge[i].w;		}        sort(edge, edge+1, cmp );		for(j=0; j<=n; j++)		{			father[j]=j;			son[j]=j;		}		cnt=0;		sum=0;		int flag=0;		for(i=0; i<m; i++)		{				if(join(edge[i].u, edge[i].v))			{				cnt++;				sum+=edge[i].w;			}			if(cnt==m-1)			{				flag=1;				break;			}		}		if(flag)		{			cout<<sum<<endl;		}	}	return 0;}//////////////////////////////////*#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>using namespace std;#define MAX 1000int father[MAX], son[MAX];int v, l;typedef struct Kruskal //存储边的信息 这样的话结构体根据边值 排序{ 	int a;	int b;	int value;};bool cmp(const Kruskal & a, const Kruskal & b){	return a.value < b.value;}int unionsearch(int x) //查找根结点+路径压缩{	return x == father[x] ? x : unionsearch(father[x]);}bool join(int x, int y) //合并{	int root1, root2;	root1 = unionsearch(x);	root2 = unionsearch(y);	if(root1 == root2) //为环		return false;	else if(son[root1] >= son[root2])		{			father[root2] = root1;			son[root1] += son[root2];		}		else		{			father[root1] = root2;			son[root2] += son[root1];		}	return true;}int main(){	int ncase, ltotal, sum, flag;	Kruskal edge[MAX];	scanf("%d", &ncase);	while(ncase--)	{		scanf("%d %d", &v, &l); //v个顶点 l条边		ltotal = 0, sum = 0, flag = 0;		for(int i = 1; i <= v; ++i) //初始化 并查集数组初始化		{			father[i] = i;			son[i] = 1;		}		for(int i = 1; i <= l ; ++i) //读入点 边 权，存入结构体，等待排序		{			scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].value);		}		sort(edge + 1, edge + 1 + l, cmp); //按权值由小到大排序		for(int i = 1; i <= l; ++i) //循环 这l条边（注意已排好序 从权值最小的边开始 ）		{			if(join(edge[i].a, edge[i].b) ) //如果加入该条边是合法的			{				ltotal++; //边数加1				sum += edge[i].value; //记录权值之和				cout<<edge[i].a<<"->"<<edge[i].b<<endl;			}			if(ltotal == v - 1) //最小生成树条件：边数=顶点数-1 边的总数可能很多，当已经加入n-1条边后就可以直接跳出了			{				flag = 1;				break;			}		}		if(flag) 			printf("%d\n", sum);		else 			printf("data error.\n");	}	return 0;}  */