还有克鲁斯卡尔

poj - 1258
居然不说是多组样例.......

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 100005
int n;
int Count;
int pre[100005];
struct node
{
    int v;
    int w;
    int edge;
}s[100005];
bool cmp(node a,node b)
{
    return a.edge<b.edge;
}
void unit()
{
    for(int i=0;i<INF;i++)
    {
        pre[i]=i;
    }
}
int find(int x)
{
    if(pre[x]==x)
    return x;
    else
    return find(pre[x]);
}
int Union(int a,int b)
{
    int X=find(a);
    int Y=find(b);
    if(X!=Y)
    {
        pre[X]=Y;
    }
     pre[a]=find(a);
pre[b]=find(b);
}
void krual()
{
    int sum=0;
    int num=0;
    for(int i=0;i<Count;i++)
    {
        if(find(s[i].v)!=find(s[i].w))
        {
            sum=sum+s[i].edge;
            num++;
            Union(find(s[i].v),find(s[i].w));
        }
        if(num>=n-1)
        {   printf("%d\n",sum);
        break;
    }
    }
}
int main()
{
   while(scanf("%d",&n)!=EOF)
   {
    Count=0; 
   int x;
   unit();
   for(int i=0;i<n;i++)
   {
    for(int  j=0;j<n;j++)
    {
        if(i>j)
        {
        scanf("%d",&s[Count].edge);
        s[Count].v=i;
        s[Count].w=j;
        Count++;
        }
        else
        scanf("%d",&x);
        
    }
   }    
   sort(s,s+Count,cmp);
   krual();
   }
}