kruskal + 并查集:计算最小生成树

编辑于 2017-01-06

* 移动设备下, 可左滑手指以查看较宽代码

题目

现在有孤岛 n 个,孤岛从 1 开始标序一直到 n ,有道路 m 条(道路是双向的,如果有多条道路连通岛屿 i,j 则选择最短的那条),请你求出能够让所有孤岛都连通的最小道路总长度。

输入有多组数据,每组第一行输入 n, m。接着 m 行,每行输入一条道路 i j d(0<=n, m, d<=1000),(i,j表示岛屿序号,d表示道路长度)。对每组输入输出一行,如果能连通,输出能连通所有岛屿的最小道路长度,否则请输出字符串"no"。

样例输入

3 5
1 2 2
1 2 1
2 3 5
1 3 3
3 1 2
4 2
1 2 3
3 4 1

样例输出

3
no

代码

#include<iostream>
#include<algorithm>
using namespace std;

struct Edge
{
    int x;
    int y;
    int cost;
} edge[10001];
int set[10001];

// 并查集查找
int find(int x)
{
    if(set[x]==x)
        return x;
    else
        // 路径压缩:把遇到的元素改为祖先,加快后面的找祖先速度
        return set[x]=find(set[x]);
}

// 并查集归并
void merge(int x,int y)
{
    if(t!=h)
        set[t]=h;
}


bool cmp(const Edge &a,const Edge &b)
{
    return a.cost<b.cost;
}

// 并查集初始化,各点为孤立点
void init(int n)
{
    for(int i=1;i<=n;i++)
        set[i]=i;
}
int kruskal(int n,int m)
{
    int i,num,sum,from,to;

    sort(edge,edge+m,cmp);
    sum=num=0;
    for(i=0;i<m;i++) {
        from = find(edge[i].x);
        to = find(edge[i].y);

        // 如果线段的两个端点所在的集合不一样
        if(from != to) {
            merge(from,to);
            sum+=edge[i].cost;
            num++;
        }
        if(num==n-1)
            break;
    }
    if(num<n-1)
        return -1;
    else
        return sum;
}

int main(void)
{
    int i,n,m,k;
    while(scanf("%d %d",&n,&m)!=EOF) {
        init(n);
        for(i=0;i<m;i++)
            scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].cost);

        k=kruskal(n,m);
        if(k==-1)
            printf("no\n");
        else
            printf("%d\n",k);
    }
    return 0;
}