题解 | #继续畅通工程#

继续畅通工程

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

#include <stdio.h>
#include <stdlib.h>

struct Edge {
    int from;
    int to;
    int cost;
    int build;
};

int father[100];
struct Edge e[100 * 100];
int height[100];

void initial(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}



int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] < height[b])
            father[a] = b;
        else if (height[a] > height[b])
            father[b] = a;
        else {
            father[a] = b;
            height[b]++;
        }
    }
}

int cmp(const void* a, const void* b) {
    const struct Edge* a1 = (const struct Edge*)a;
    const struct Edge* b1 = (const struct Edge*)b;
    if (a1->cost > b1->cost)
        return 1;
    if (a1->cost < b1->cost)
        return -1;
    return 0;
}

void initialF(struct Edge e[], int m){
    for(int i = 0; i < m; i++){
        if (e[i].build == 1){
            Union(e[i].from, e[i].to);
        }
    }
}

int KrusKal(struct Edge e[], int m) {
    initialF(e, m);
    int ans = 0;
    qsort(e, m, sizeof(struct Edge), cmp);
    for (int i = 0; i < m; i++) {
        if (Find(e[i].to) != Find(e[i].from) && e[i].build == 0) {
            Union(e[i].to, e[i].from);
            ans += e[i].cost;
        }
    }
    return ans;
}

int main() {
    int n, m, count = 0, f, t, c, bui;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        initial(n);
        m = n * (n - 1) / 2;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d", &f, &t, &c, &bui);
            e[i].to = t;
            e[i].from = f;
            e[i].cost = c;
            e[i].build = bui; // 初始化build值
        }
        // for (int i = 0; i < m; i++){
        //     printf("%d", e[i].build);
        // }
        int res = KrusKal(e, m);
        printf("%d\n", res);
    }
    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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