镖局运镖 (并查集)"/>
镖局运镖 (并查集)
镖局的运镖,就是运货(类似现在的物流)。镖局每到一个新地方开展业务,都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低,不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线,已知城市的地图,你需要选择一些道路进行疏通,以便镖局可以到达任意一个城市,要求花费的银子越少越好。
输入格式:
第一行有两个数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");
}
更多推荐
镖局运镖 (并查集)
发布评论