poj 1789 Truck History(kruskal算法實現)

怎麼我的算法時間和空間都這麼就，別人的kruskal還是比較快的！ 去學習一下！

   /*kruskal算法*/ 
#include <iostream>  
//#include <fstream>  
#include <algorithm>   
using namespace std; 
#define MAX 2001  
#define min(a,b)  (a-b<0?a:b)  
 
/*45612K    1563MS*/ 
typedef struct _node 
{ 
        int x,y; 
        int weight; 
}node; 
 
int n; 
char a[MAX][8]; 
int sum; 
//fstream fin;  
 
void kruskal(node *a,int index); 
int GetDis(int x,int y); 
int cmp(const void *a,const void *b); 
 
int main() 
{ 
    //fin.open("1789.txt",ios::in);  
    while(cin>>n) 
    { 
         if(n==0)  break; 
         sum=0; 
         for(int i=0;i<n;i++) 
            cin>>a[i]; 
         //計算邊的信息  
         node *a=new node[n*n];  
         node temp; 
         int index=0; 
         for(int i=0;i<n;i++) 
            for(int j=0;j<n;j++) 
            { 
                    temp.x=i; 
                    temp.y=j; 
                    temp.weight=GetDis(i,j); 
                    a[index++]=temp; 
            } 
 
         kruskal(a,index); 
         cout<<"The highest possible quality is 1/"<<sum<<"."<<endl;  
         delete []a;         
    } 
    system("pause"); 
    return 0; 
} 
 
int GetDis(int x,int y) 
{ 
    int count=0; 
    for(int i=0;i<7;i++) 
       if(a[x][i]!=a[y][i]) 
         ++count; 
 
    return count; 
} 
 
int cmp(const void *a,const void *b) 
{ 
    node a1=*(node *)a; 
    node b1=*(node *)b; 
    return (a1.weight-b1.weight); 
} 
 
void kruskal(node *a,int index) 
{ 
     //排序  
     qsort(a,index,sizeof(node),cmp); 
     int *s=new int[n]; 
     memset(s,0,sizeof(int)*n); 
     int parts=0;  //分支數   
     for(int i=0;i<index;i++) 
     { 
             if(a[i].weight==0)  continue; 
             int u,v; 
             u=a[i].x;v=a[i].y; 
             //判斷u，v在位置上  
            if(!s[u]&&!s[v])  
             { 
                  parts++; 
                  s[u]=parts; 
                  s[v]=parts; 
                  sum+=a[i].weight; 
             } 
             else  if(s[u]&&!s[v]) 
             { 
                   s[v]=s[u]; 
                   sum+=a[i].weight; 
             } 
             else if(s[v]&&!s[u]) 
             { 
                   s[u]=s[v]; 
                   sum+=a[i].weight; 
             } 
             else 
             { 
                 if(s[u]!=s[v])  //不在同一個分支上   
                 { 
                       //計算最小的分支  
                       int min=s[u]; 
                       int max=s[v]; 
                       if(s[v]>s[u]) 
                       { 
                          min=s[v]; 
                          max=s[u]; 
                       }  
                       for(int j=0;j<n;j++) 
                       { 
                           if(s[j]==max) 
                             s[j]=min; 
                           if(s[j]>max) 
                             s[j]--; 
                       } 
                       parts--;  
                       sum+=a[i].weight; 
                 } 
             } 
     } 
      
     delete []s; 
          
} 

/*kruskal算法*/
#include <iostream>
//#include <fstream>
#include <algorithm>
using namespace std;
#define MAX 2001
#define min(a,b)  (a-b<0?a:b)

/*45612K 1563MS*/
typedef struct _node
{
        int x,y;
        int weight;
}node;

int n;
char a[MAX][8];
int sum;
//fstream fin;

void kruskal(node *a,int index);
int GetDis(int x,int y);
int cmp(const void *a,const void *b);

int main()
{
    //fin.open("1789.txt",ios::in);
    while(cin>>n)
    {
         if(n==0)  break;
         sum=0;
         for(int i=0;i<n;i++)
            cin>>a[i];
         //計算邊的信息
         node *a=new node[n*n];
         node temp;
         int index=0;
         for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                    temp.x=i;
                    temp.y=j;
                    temp.weight=GetDis(i,j);
                    a[index++]=temp;
            }

         kruskal(a,index);
         cout<<"The highest possible quality is 1/"<<sum<<"."<<endl;
         delete []a;       
    }
    system("pause");
    return 0;
}

int GetDis(int x,int y)
{
    int count=0;
    for(int i=0;i<7;i++)
       if(a[x][i]!=a[y][i])
         ++count;

    return count;
}

int cmp(const void *a,const void *b)
{
    node a1=*(node *)a;
    node b1=*(node *)b;
    return (a1.weight-b1.weight);
}

void kruskal(node *a,int index)
{
     //排序
     qsort(a,index,sizeof(node),cmp);
     int *s=new int[n];
     memset(s,0,sizeof(int)*n);
     int parts=0;  //分支數
     for(int i=0;i<index;i++)
     {
             if(a[i].weight==0)  continue;
             int u,v;
             u=a[i].x;v=a[i].y;
             //判斷u，v在位置上
            if(!s[u]&&!s[v])
             {
                  parts++;
                  s[u]=parts;
                  s[v]=parts;
                  sum+=a[i].weight;
             }
             else  if(s[u]&&!s[v])
             {
                   s[v]=s[u];
                   sum+=a[i].weight;
             }
             else if(s[v]&&!s[u])
             {
                   s[u]=s[v];
                   sum+=a[i].weight;
             }
             else
             {
                 if(s[u]!=s[v])  //不在同一個分支上
                 {
                       //計算最小的分支
                       int min=s[u];
                       int max=s[v];
                       if(s[v]>s[u])
                       {
                          min=s[v];
                          max=s[u];
                       }
                       for(int j=0;j<n;j++)
                       {
                           if(s[j]==max)
                             s[j]=min;
                           if(s[j]>max)
                             s[j]--;
                       }
                       parts--;
                       sum+=a[i].weight;
                 }
             }
     }
    
     delete []s;
        
}