Kurskal算法

80 阅读 0 评论 53 点赞

我是靠谱客的博主震动大神，最近开发中收集的这篇文章主要介绍Kurskal算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

Sample Output

3
5

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include"vector"
#include<stack>
#include "queue"
using namespace std;
int per[5005];
int m;
struct ac{
    int s;
    int e;
    int l;
}road[5005];
int cmp(ac x,ac y)
{
    return x.l<y.l;
}
void dui()
{
    for(int i=1;i<=m;i++)
        per[i]=i;
}
int find(int x)
{
    if(per[x]==x)
    return x;
    return per[x]=find(per[x]);//路径压缩
}
bool link(int x,int y)
{
    int nx=find(x),ny=find(y);
    if (nx!=ny) {
        per[ny]=nx;
        return 1;
    }
    return 0;
    
}
int main()
{
    int n;
    while (scanf("%d",&n)) {
        if (n==0) {
            break;
        }
        m=n*(n-1)/2;
        memset(road,0,sizeof(road));
        memset(per,0,sizeof(per));
        dui();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&road[i].s,&road[i].e,&road[i].l);
        }
        sort(road+1,road+1+m,cmp);
        int sum=0;
        for(int i=1;i<=m;i++)
        {
            if (link(road[i].s,road[i].e)){
                sum+=road[i].l;
            }

        }
        printf("%dn",sum);
    }
    return 0;
    
}