poj 1789 truck history

一道很扯淡的英語題目。這個題目的意思其實我也沒怎麼搞明白但是看出來是最小生成樹，然後直接prim算法就解決了。稀裡糊塗的就解決了，呵呵。

[cpp]  <SPAN style="FONT-SIZE: 18px">#include<iostream> 
#include<string>  
#include<cstring>  
using namespace std; 
string str[2005]; 
int map[2005][2005]; 
int vis[2005]; 
int main() 
{ 
    int n,i,j,sum,k,flag,mini; 
    while(cin>>n) 
    { 
        if(n==0) 
            break; 
        sum=0; 
        for(i=1;i<=n;i++) 
            cin>>str[i]; 
        memset(map,10,sizeof(map)); 
        memset(vis,0,sizeof(vis)); 
        for(i=1;i<=n;i++) 
            for(j=1;j<i;j++) 
            { 
                map[i][j]=0; 
                for(k=0;k<7;k++) 
                    if(str[i][k]!=str[j][k]) 
                        map[i][j]=map[i][j]+1; 
                map[j][i]=map[i][j]; 
            } 
        for(i=1;i<=n;i++) 
            map[i][i]=10; 
        vis[1]=1; 
        for(i=2;i<=n;i++) 
        { 
            mini=10; 
            for(j=1;j<=n;j++) 
                if(vis[j]==0&&map[1][j]<mini) 
                { 
                    flag=j; 
                    mini=map[1][j]; 
                } 
            vis[flag]=1; 
            sum=sum+mini; 
            for(j=1;j<=n;j++) 
                if(vis[j]==0&&map[1][j]>map[flag][j]) 
                    map[1][j]=map[flag][j]; 
        } 
        cout<<"The highest possible quality is "<<"1/"<<sum<<"."<<endl; 
    } 
    return 0; 
} 
 
 
 
 
 
</SPAN> 

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string str[2005];
int map[2005][2005];
int vis[2005];
int main()
{
 int n,i,j,sum,k,flag,mini;
 while(cin>>n)
 {
  if(n==0)
   break;
  sum=0;
  for(i=1;i<=n;i++)
   cin>>str[i];
  memset(map,10,sizeof(map));
  memset(vis,0,sizeof(vis));
  for(i=1;i<=n;i++)
   for(j=1;j<i;j++)
   {
    map[i][j]=0;
    for(k=0;k<7;k++)
     if(str[i][k]!=str[j][k])
      map[i][j]=map[i][j]+1;
    map[j][i]=map[i][j];
   }
  for(i=1;i<=n;i++)
   map[i][i]=10;
  vis[1]=1;
  for(i=2;i<=n;i++)
  {
   mini=10;
   for(j=1;j<=n;j++)
    if(vis[j]==0&&map[1][j]<mini)
    {
     flag=j;
     mini=map[1][j];
    }
   vis[flag]=1;
   sum=sum+mini;
   for(j=1;j<=n;j++)
    if(vis[j]==0&&map[1][j]>map[flag][j])
     map[1][j]=map[flag][j];
  }
  cout<<"The highest possible quality is "<<"1/"<<sum<<"."<<endl;
 }
 return 0;
}