/*
合并时候出了问题，还有把所有0置无穷大；
*/
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace    std;

struct Tree
{
    int ss;
    int ee;
    int ll;
};

const int MM = 2147483600;

Tree T[5005];
int F[105],A[105][105];

inline int KP(const void *a,const void *b)
{
    return (*(Tree *)a).ll - (*(Tree *)b).ll;
}

inline void reading(int  N)
{
    int i,j;
    for(i=1;i<=N;i++)
    {
        F[i]=i;
        for(j=1;j<=N;j++)
        {
            scanf("%d",&A[i][j]);
            if(A[i][j]==0)
            {
                A[i][j]=MM;
            }
        }
    }
}

inline void setting(int  N)
{
    int i,j,k=0;
    
    for(i=2;i<=N;i++)
    {
        for(j=1;j<i;j++)
        {
            T[k].ll = A[i][j];
            T[k].ss = i;
            T[k].ee = j;
            k++;
        }
    }
}

inline int  finding(int  N)
{
    if(N != F[N])
    {
        F[N] = finding(F[N]);
    }
    return F[N];
}

inline void putting(int  x, int  y)
{
    int xx = finding(x);
    int yy = finding(y);
    if(xx < yy)
    {
        F[xx] = yy;
    }
    else if(xx > yy)
    {
        F[yy] = xx;
    }
}

int main()
{
    int I,n,count,summm,nummm;
    while(scanf("%d",&n) != EOF)
    {
        
        if(n==1 || n==0)
        {
            printf("0\n");
        }
        
        else
        {
        
        I=0;
        count=1;
        summm=0;
        nummm=(n*n-n)/2;
        
        reading(n);
        setting(n); 
        qsort(T,nummm,sizeof(T[0]),KP);
        while(count != n)
        {
            if( finding(T[I].ss) != finding(T[I].ee) )
            {
                summm=summm+T[I].ll;
                putting(T[I].ss,T[I].ee);
                count++;
            }
            I++;
        }
        printf("%d\n",summm);
        }
    }
    return 0;
}

• Re:poj有一种编程人的文化！！！！！！！！！—— (4) 20091101579 2011-01-01 10:29:45