镖局运镖 (并查集)

镖局运镖 (并查集)"/>

镖局运镖 (并查集)

镖局的运镖，就是运货（类似现在的物流）。镖局每到一个新地方开展业务，都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低，不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线，已知城市的地图，你需要选择一些道路进行疏通，以便镖局可以到达任意一个城市，要求花费的银子越少越好。

输入格式:
第一行有两个数n和m，n表示有n个城市（编号从1到n），m表示有m条道路。接下来m行，每行形如“a b c”用来表示一条道路，意思是城市a到城市b连通且打点需要花费的银子数是c。

输出格式:
若通过打点能抵达所有城市，则输出最少需要花费的银子总数。若不能抵达所有的城市则输出“impossible”。

输入样例:
3 3
1 2 1
1 3 2
2 3 4

输出样例:
3

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{int u,v,len;
}a[3005];
int cmp(node x,node y)
{return x.len<y.len;
}
int f[1005];
int find(int x)
{if(x!=f[x])f[x]=find(f[x]);return f[x];
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=0;i<m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].len);sort(a,a+m,cmp);for(int i=0;i<n;i++)f[i]=i;int ans=0;for(int i=0;i<m;i++){int fa=find(a[i].u);int fb=find(a[i].v);if(fa!=fb){if(fa>fb)f[fa]=fb;elsef[fb]=fa;n--;ans+=a[i].len;}}if(n==1) printf("%d\n",ans);else printf("impossible\n");
}