Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
小弟十万真心求教:I'm恭候ing.........#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++)//3<=N<=100!!!这样可以吧? { 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] = (xx<yy)?xx:yy; } } 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; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator