首页 > 代码库 > POJ 1258-Agri-Net (Kruskal)

POJ 1258-Agri-Net (Kruskal)

题目链接:Agri-Net


最小生成树水题,数组开的和题目描述一样,但是就是RE,有填了个0,还好这个题用 库鲁斯卡尔 敲了一遍,发现了点问题,以前写的库鲁卡尔模板有点问题,多写了步无用的操作,已修正。

题意:就是一个农夫想选镇长。。。。建一条路,使之能到达所有点,距离最短。

scanf输入

796K32MS

cin输入

832K125MS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int N = 11000;
using namespace std;
int n,ans,l;
struct node{
    int u,v,w;
}edge[10000];
int father[N];
int cmp(const void *a,const void *b)
{
    node *X = (struct node *)a;
    node *Y = (struct node *)b;
    return X->w - Y->w;
}
int find(int x)
{
    return (father[x]==x)?(x):find(father[x]);
}

void Kruskal()
{
    ans = 0;
    int uu,vv;
     for(int i = 0;i<n;i++)
        father[i] = i;
    for(int i = 0;i<l;i++)
    {
         uu = find(edge[i].u);
         vv = find(edge[i].v);
         if(uu!=vv)
         {
             father[uu] = vv;
             ans += edge[i].w;
         }
    }
    cout<<ans<<endl;
}
int main()
{
    int a;
    while(cin>>n)
    {
        l = 0;
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<n;j++)
            {
                cin>>a;
                edge[l].u = i; edge[l].v = j; edge[l].w = a;
                l++;
            }
        }
        qsort(edge,l,sizeof(edge[0]),cmp);
        Kruskal();
    }
    return 0;
}


832K125MS