Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小弟十万真心求教:I'm恭候ing.........

Posted by 20091101579 at 2011-01-01 09:55:13 on Problem 1258
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator