#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef struct
{
    int x,y,len;
}Node;

int n,k;
Node road[100000];
int father[100000];

int find(int x)
{
    while (father[x]!=x)
    {
        x=father[x];
    }
    return x;
}

int cmp(Node a,Node b)
{
    return (a.len<b.len);
}

long long  Kruskal()
{
    int a,b,count;
    long long sum=0;
    sort(road+1,road+1+k,cmp);
    for (int i=1;i<=n;i++) father[i]=i;
    for (int i=1;i<=k;i++)
    {
        if (road[i].x==road[i].y) continue;
        a=find(road[i].x);
        b=find(road[i].y);
        if (a!=b)
        {
            sum+=road[i].len;
            father[b]=a;
            count++;
        }
        if (count==n-1) break;
    }
    return sum;
}

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        int tmp;
        k=1;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                scanf("%d",&tmp);
                road[k].x=i;
                road[k].y=j;
                road[k].len=tmp;
                k++;
            }
        }
        cout<<Kruskal()<<endl;
    }
    return 0;
}

• Re:Kruskal 并查集做的 为神马wa ... (1357) Azure_Air 2013-04-12 19:32:13
  • Re:Kruskal 并查集做的 为神马wa ... (16) Azure_Air 2013-04-12 19:32:55
• Re:Kruskal 并查集做的 为神马wa ... (1357) fisty 2014-08-07 21:34:47
  • Re:Kruskal 并查集做的 为神马wa ... (48) fisty 2014-08-07 21:38:48