例题：联络员

#include <bits/stdc++.h>//采用Kruskal算法 
using namespace std;

int n,m,p,fa[10005],ans;
struct node//路径 
{
	int s,e,w;
} a[10005];

bool cmp(node a, node b)//结构体排序 
{
	return a.w < b.w;
}

int find(int x)//寻找该点的根节点并在沿途中压缩路径 
{
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

void unionn(int x, int y)
{
	x = find(x);
	y = find(y);
	fa[y] = x;
} 

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) fa[i] = i;//初始化 
	for (int i = 1; i <= m; i++)
	{
		cin >> p >> a[i].s >> a[i].e >> a[i].w;
		int x = find(a[i].s), y = find(a[i].e);
		if (p == 1)//如果是必选路线就合并并查集，并将权值加在结果上 
		{
			unionn(x,y);
			ans += a[i].w;
		}
	}
	sort(a+1, a+m+1, cmp);
	for (int i = 1; i <= m; i++)
	{
		int x = find(a[i].s), y = find(a[i].e);
		if (x != y)//Kruskal算法中判断该边是否会造成回环 
		{
			unionn(x,y);
			ans += a[i].w;
		}
	}
	cout << ans << endl;
	return 0;
}