首页 > 代码库 > hdu 1233 还是畅通工程

hdu 1233 还是畅通工程

简单最小生成树,继续我的kruskal

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX=1000000;
struct node
{
    int left,right,cost;
}road[MAX];

bool cmp(node x,node y){return x.cost<y.cost;}

int p[MAX],m,n;

int find(int x){return x==p[x]? x:p[x]=find(p[x]);}

int kruskal()
{
    int ans=0;
    for (int i=0;i<=n;i++) p[i]=i;
    for (int i=0;i<(n*(n-1))/2;i++)
    {
        int x=find(road[i].left);
        int y=find(road[i].right);
        if(x!=y)
        {
            ans+=road[i].cost;
            p[x]=y;
        }
    }
    return ans;
}

int main()
{
    int x,y,c;
    while(scanf("%d",&n)!=EOF && n)
    {
        for (int i=0;i<(n*(n-1))/2;i++)
        scanf("%d%d%d",&road[i].left,&road[i].right,&road[i].cost);
        sort(road,road+(n*(n-1))/2,cmp);
        int mintree=kruskal();
        printf("%d\n",mintree);
    }
    return 0;
}