/*
LZ 2010-04-09 11:24:28
Memory Time 
296K   32MS 
*/
#include<iostream> 
using namespace std;
const int M=101*50+1,L=101;
int n,t,s,Rootx,Rooty,num;
int Sum;
struct MFTNode{
        int x,y;
        int w;
        }f[M];
int FATHER[L];

int comp(const void*a,const void*b){
    MFTNode *m,*n;
    m=(MFTNode*)a;
    n=(MFTNode*)b;
    return m->w>n->w?1:-1;
    }

void init_fopen(void){
     freopen ("PKU_1258.in","r",stdin);
     freopen ("PKU_1258.out","w",stdout);
     }

void solve_init(void){
     s=0;
     Sum=0;num=0;
     memset(FATHER,0,sizeof (FATHER));
     for (int i=1;i<=n;i++){
         for (int j=1;j<=i;j++)scanf ("%d",&t);
         for (int j=i+1;j<=n;j++){
             scanf ("%d",&f[++s].w);
             f[s].x=i;f[s].y=j;
             }
         }
     qsort (f+1,s,sizeof (f[0]),comp);   
     }

int find(int k){
    if(!FATHER[k]) return k;
    return FATHER[k]=find(FATHER[k]);
    }

int main(void){
    init_fopen();
    while (cin>>n){          
          solve_init();
          s=1;
          while (num<n-1){
              Rootx=find(f[s].x);
              Rooty=find(f[s].y);
              if(Rootx!=Rooty){
                 num++;
                 Sum+=f[s].w;
                 FATHER[Rooty]=Rootx;
                 }   
              s++;
              }
          printf ("%d\n",Sum);
          }
    return 0;
    }

• Re: C++ 1258 LZ (1558) jianniaoru 2010-04-09 11:29:31
• Re: C++ 1258 LZ (1558) jianniaoru 2010-04-09 11:29:39