/*kruskal算法思想：每次選擇圖中最小邊權(quán)的邊，如果邊兩端的頂點(diǎn)在不同的連通塊中，就把這條邊加入最小生成樹中。kruskal偽代碼如下：int kruskal(){	令最小生成樹的邊權(quán)之和為ans、最小生成樹的當(dāng)前邊數(shù)Num_Edge;	將所有邊按邊權(quán)從小到大排序；	for(從小到大枚舉所有邊)	{		if(當(dāng)前測試邊的兩個端點(diǎn)在不同的連通塊中)		{			將該測試邊加入最小生成樹中；			ans+=測試邊的邊權(quán)；			最小生成樹的當(dāng)前邊數(shù)Num_Edge加1；			當(dāng)邊數(shù)Num_Edge等于頂點(diǎn)數(shù)減1時結(jié)束循環(huán)；		}	}	return ans;}*///kruskal算法應(yīng)用實(shí)現(xiàn)代碼#include<cstdio>#include<algorithm>using namespace std;const int MAXV = 110;const int MAXE = 10010;//邊集定義部分struct edge{	int u, v;//邊的兩個端點(diǎn)編號	int cost;//邊權(quán)}E[MAXE];//最多有MAXE邊bool cmp(edge a, edge b){	return a.cost < b.cost;}//并查集部分int father[MAXV];//并查集數(shù)組/*int findFather(int x)//并查集查詢函數(shù){	int a = x;	while (x != father[x])	{		x = father[x];	}	//路徑壓縮	while (a != father[a])	{		int z = a;		a = father[a];		father[z] = x;	}	return x;}*/int findFather(int x)//遞歸版{	if (x == father[x])		return x;	else	{		int f = findFather(father[x]);		father[x] = f;		return f;	}}//kruskal部分，返回最小生成樹的邊權(quán)之和，參數(shù)n為頂點(diǎn)個數(shù)，m為圖的邊數(shù)int kruskal(int n, int m){	//ans為所求邊權(quán)之和，Num_Edge為當(dāng)前生成樹的邊數(shù)	int ans = 0, Num_Edge = 0;	for (int i = 0; i < n; i++)//頂點(diǎn)范圍是[0,n-1]	{		father[i] = i;//并查集初始化	}	sort(E, E + m, cmp);//所有邊按邊權(quán)從小到大排序	for (int i = 0; i < m; i++)//枚舉所有邊	{		int faU = findFather(E[i].u);//查詢測試邊兩個端點(diǎn)所在集合的根結(jié)點(diǎn)		int faV = findFather(E[i].v);		if (faU != faV)//如果不在一個集合中		{			father[faU] = faV;//合并集合(即把測試邊加入最小生成樹中)			ans += E[i].cost;//邊權(quán)之和增加測試邊的邊權(quán)			Num_Edge++;//當(dāng)前生成樹的邊數(shù)加1			if (Num_Edge == n - 1)break;//邊數(shù)等于頂點(diǎn)數(shù)減1時結(jié)束算法		}	}	if (Num_Edge != n - 1)return -1;//無法連通時返回-1	else return ans;//返回最小生成樹的邊權(quán)之和}int main(){	int n, m;	scanf("%d%d", &n, &m);//頂點(diǎn)數(shù)，邊數(shù)	for (int i = 0; i < m; i++)	{		scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);//兩個端點(diǎn)的編號、邊權(quán)	}	int ans = kruskal(n, m);//kruskal算法入口	PRintf("%d/n", ans);	return 0;}