7-13 镖局运镖 (10 分)
镖局的运镖，就是运货（类似现在的物流）。镖局每到一个新地方开展业务，都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低，不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线，已知城市的地图，你需要选择一些道路进行疏通，以便镖局可以到达任意一个城市，要求花费的银子越少越好。
输入格式:
第一行有两个数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<iostream> #include<algorithm> using namespace std; const int N=1e5+10; int n,m,p[N],cnt,sum; struct ll{ int a,b,c; }q[N]; int find(int x){ if(x!=p[x])p[x]=find(p[x]); return p[x]; } bool cmp(ll x,ll y){ return x.c<y.c; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++)p[i]=i; for(int i=0;i<m;i++)cin>>q[i].a>>q[i].b>>q[i].c; sort(q,q+m,cmp); for(int i=0;i<m;i++){ if(find(q[i].a)!=find(q[i].b)){ p[find(q[i].a)]=find(q[i].b); sum+=q[i].c; } } for(int i=1;i<=n;i++)if(find(i)==i)cnt++; if(cnt==1)cout<<sum; else cout<<"impossible"; return 0; }
结尾无空行
