首页 > 代码库 > UESTC 918 WHITE ALBUM --生成树变形
UESTC 918 WHITE ALBUM --生成树变形
最小生成树变形。
题目已经说得很清楚,要求到达每个房间,只需求一个最小生成树,这时边权和一定是最小的,并且那k个房间一定与所有点都有通路,即一定都可以逃脱。
但是有可能当所有点都有了该去的安全房间以后,安全房间之间并不需要连边了,这样就会变成多个树,不好处理。想一想,既然不需要连边了,也就是边权不再增加,如果将他们之间的边权变为0,也可以起到不增加边权的作用,并且可以将他们联通成一棵生成树了。所以,可以将k个点都通过一条边权为0的边,连到一个不在图中的点上,这样都可以联通了,在求一个最小生成树即可。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 1007int fa[N];int n,m,k;int res;struct Edge{ int u,v,w;}G[N*N/2];int cmp(Edge ka,Edge kb){ return ka.w < kb.w;}int findset(int x){ if(x != fa[x]) fa[x] = findset(fa[x]); return fa[x];}void Kruskal(){ int i,j,cnt = m+k; sort(G,G+cnt,cmp); for(i=0;i<=n;i++) fa[i] = i; res = 0; for(i=0;i<cnt;i++) { int u = G[i].u; int v = G[i].v; int fx = findset(u); int fy = findset(v); if(fx != fy) { res += G[i].w; fa[fx] = fy; } }}int main(){ int i,j,a,b,c,x; scanf("%d%d%d",&n,&m,&k); for(i=0;i<k;i++) { scanf("%d",&x); G[i].u = x; G[i].v = 0; G[i].w = 0; } for(i=k;i<m+k;i++) { scanf("%d%d%d",&a,&b,&c); G[i].u = a; G[i].v = b; G[i].w = c; } Kruskal(); printf("%d\n",res); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。