还是畅通工程

[编程题]还是畅通工程

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

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入描述:

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
    当N为0时，输入结束，该用例不被处理。

输出描述:

    对每个测试用例，在1行里输出最小的公路总长度。

示例1

输入

输出

3
5

算法知识视频讲解

chong_0428

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

struct Point{
    int x;
    int y;
};
struct Edge{
    int from;
    int to;
    int length;
};

struct Point point[100];
struct Edge edge[100*99/2];
int father[100];
int heigth[100];
void initial(int n){
    int i;
    for (i = 0; i < n; i++){
        father[i] = i;
        heigth[i] = 0;
    }
        
}

int Find(int i){

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

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

int cmp(const void *a, const void *b){
    const struct Edge*edga = (const struct Edge*)a;
    const struct Edge*edgb = (const struct Edge*)b;
    if(edga->length < edgb->length) return -1;
    if (edga->length > edgb->length) return 1;
    return 0;
    
}
int kruskal(int n, int edgenum){
    initial(n);
    int ans = 0;
    qsort(edge, edgenum, sizeof(struct Edge), cmp);
    for (int i = 0; i < edgenum; i++){
        if (Find(edge[i].from) != Find(edge[i].to)){
            Uion(edge[i].from, edge[i].to);
                ans += edge[i].length;
        }
    }
    return ans;

}



int main(){
    int n, res;
    int a[100];
    while(scanf("%d", &n) != EOF){
        if (n == 0) break;
        for(int i = 0; i < n*(n-1)/2; i++){
            scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].length);
        }
        res = kruskal(n, n*(n-1)/2);
        printf("%d\n", res);
    }
    return 0;
}

发表于 2025-02-25 21:05:02 回复(0)