> #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 ... (16) Azure_Air 2013-04-12 19:32:55