首页 > 代码库 > UESTC 918 WHITE ALBUM --生成树变形

UESTC 918 WHITE ALBUM --生成树变形

2024-07-08 07:01:33   223人阅读

最小生成树变形。

题目已经说得很清楚，要求到达每个房间，只需求一个最小生成树，这时边权和一定是最小的，并且那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;}
View Code

 

 


联系
我们