30分,用的最小生成树,求助
  • 板块P1262 间谍网络
  • 楼主Morax_
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/10 18:01
  • 上次更新2023/10/28 04:03:32
查看原帖
30分,用的最小生成树,求助
617672
Morax_楼主2022/4/10 18:01

KruskalKruskal 算法,不知道哪里有问题

#include<stdio.h>
#include<algorithm>
struct KJF{
    int can,data;
}a[3005];
struct Kangjf{
    int x,y,s;
}edge[8005];
int f[8005];
inline int Find(int x){if(x!=f[x])f[x]=Find(f[x]);return f[x];}
inline void Union(int x,int y){f[Find(y)]=Find(x);}
inline bool cmp(Kangjf x,Kangjf y){return x.s<y.s;}
int main(){
    int n,p,r,tmp,ret=0;
    scanf("%d%d",&n,&p);
    for(register int i(1);i<=p;++i){
        scanf("%d",&tmp);
        a[tmp].can=1;
        scanf("%d",&a[tmp].data);
    }
    scanf("%d",&r);
    for(register int i(1);i<=r;++i){
        scanf("%d%d",&edge[i].x,&edge[i].y);
        edge[i].s=a[edge[i].x].data;
        a[edge[i].y].can=1;
    }
    for(register int i(1);i<=n;++i){
        if(a[i].can==0){
            printf("NO\n%d",i);
            return 0;
        }
    }
    printf("YES\n");
    for(register int i(1);i<=r;++i)f[i]=i;
    std::sort(edge+1,edge+r+1,cmp);
    for(register int i(1);i<=r;++i){
        int x=edge[i].x,y=edge[i].y;
        if(Find(x)==Find(y))continue;
        ret+=edge[i].s;
        Union(x,y);
    }
    printf("%d",ret);
}
2022/4/10 18:01
加载中...