题记(25)--继续畅通工程

目录

一、题目内容

二、输入描述

三、输出描述

四、输入输出示例

五、完整C语言代码

一、题目内容

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

二、输入描述

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

三、输出描述

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

四、输入输出示例

输入：

3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

输出：

3
1
0

变化不大，添加了路是否修好的状态，如果状态为1，则执行Kruskal前将对应两点先Union即可。不要忘记Union后连通分量T将减1。

五、完整C语言代码

AC代码~


#include <stdio.h>
#define nn 2000
int height[nn];
int father[nn];

typedef struct Number { // 起始点；终点；边权值
    int from;
    int to;
    int c;
    int state;
} Num;

Num N[10000];

void init(int n) { // 初始化
    for (int i = 1; i <= n; i++) {
        height[i] = 1;
        father[i] = i;
    }
}

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

void Union(int x, int y) {
    int fx = Find(x);
    int fy = Find(y);
    if (height[fx] < height[fy]) {
        father[fx] = fy;
    } else if (height[fx] > height[fy]) {
        father[fy] = fx;
    } else {
        father[fy] = fx;
        height[fx]++;
    }
}

void SortEdge(Num N[], int n) { // 将图的所有边升序排序
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (N[j].c > N[j + 1].c) {
                Num tmp = N[j];
                N[j] = N[j + 1];
                N[j + 1] = tmp;
            }
        }
    }
}

int main() {  // Kruskal算法
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0)
            break;
        for (int i = 0; i < (n * (n - 1) / 2); i++) {
            scanf("%d%d%d%d", &(N[i].from), &(N[i].to), &(N[i].c), &(N[i].state));
        }
        init(n);
        SortEdge(N, n * (n - 1) / 2);
        int T = n;      // 连通分量数 减为1时算法结束
        int i = 0;      // N[]即边数组下标
        int min_w = 0;  // 最小生成树（MST）的权值
        for (int i = 0; i < n * (n - 1) / 2; i++) {
            if (N[i].state == 1) {
                if (Find(N[i].from) != Find(N[i].to)) {
                    Union(N[i].from, N[i].to);
                    T--;
                }
            }
        }// 已修好的路连好
        while (T > 1) { // 开始用Kruskal算法求MST
            int x = N[i].from;
            int y = N[i].to;
            int c = N[i].c;
            if (Find(x) != Find(y)) {
                Union(x, y);
                min_w += c;
                T--;
            }
            i++;
        }
        printf("%d\n", min_w);
    }
    return 0;
}