最短路kruskal算法

直接上代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int Max=110000;
int fa[Max];
int find(int x)
{
    if(fa[x]==x)
        return x;
    else
        return fa[x]=find(fa[x]);
}
struct Side
{
    int r;
    int l;
    int w;
    bool operator <(const Side &ano)const
    {
        return w<ano.w;
    }
}side[Max];
int main()
{
    int m,n;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        int l,r,w;
        scanf("%d%d%d",&l,&r,&w);
        side[i].l=l;
        side[i].r=r;
        side[i].w=w;
    }
    sort(side,side+n);
    int res=0;
    for(int i=0;i<n;i++)
    {
        int fx=find(side[i].l);
        int fy=find(side[i].r);
        if(fx!=fy)
        {
            res+=side[i].w;
            fa[fx]=fy;
        }
    }
    printf("%d\n",res);
}

最短路kruskal算法,布布扣,bubuko.com

最短路kruskal算法

原文：http://blog.csdn.net/u013889359/article/details/21884493