首页 > 试题广场 >

继续畅通工程

[编程题]继续畅通工程

热度指数：10018 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

输入描述:

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

    当N为0时输入结束。

输出描述:

    每个测试用例的输出占一行，输出全省畅通需要的最低成本。

示例1

输入

输出

3
1
0

算法知识视频讲解

Python3

chong_0428

#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;
}

编辑于 2024-03-23 23:03:24 回复(0)