题解 | #继续畅通工程#

继续畅通工程

https://www.nowcoder.com/practice/16212f7d46e44174b5505997ea998538

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{
    int x;
    int y;
    int weight;
    int ok;
};
#define N 1000
int father[N];
int height[N];
void Init(int n){
    for(int i=1;i<=n;i++){
        father[i]=i;
        height[i]=1;
    }
}
int Find(int x){
    if(x!=father[x]){
        father[x]=Find(father[x]);

    }
    return father[x];
}
void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(height[x]<height[y]){
        father[x]=y;
    }
    else if(height[x]>height[y]){
        father[y]=x;
    }
    else{
        father[y]=x;
    }
}
bool cmp(Edge a,Edge b){
    return a.weight<b.weight;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            break;
        }
        int m=n*(n-1)/2;
        vector<Edge> vec;
        Init(n);
        for(int  i=0;i<m;i++){
            Edge edge;
            scanf("%d%d%d%d",&edge.x,&edge.y,&edge.weight,&edge.ok);
            vec.push_back(edge);
        }
        int tol=0;
        for(int i=0;i<m;i++){
            if(vec[i].ok==1){
                Union(vec[i].x,vec[i].y);
            }
        }

        sort(vec.begin(),vec.end(),cmp);
        for(int i=0;i<m;i++){
            if(vec[i].ok==0&&Find(vec[i].x)!=Find(vec[i].y)){
                Union(vec[i].x,vec[i].y);
                tol=tol+vec[i].weight;
            }
        }

        printf("%d\n",tol);

    }

}

全部评论

相关推荐

05-20 21:57
已编辑
门头沟学院 Java
喜欢吃卤蛋的悲伤蛙在...:建信融通没消息吧,我2说有实习挂简历不理了
点赞 评论 收藏
分享
程序员小白条:太晚了,看别人找到实习了才投的话,自己本身就没啥准备,计划太晚咯,只能吞苦果子
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务