学步园

题意：输入N，然后N行，每行输入一个长度是7的字符串，比较每个字符串上相同位置的字符，如果不同的话这两个点的距离加一

思路：prime求最小生成树，1/Q就是最大的值。

#include<iostream>
using namespace std;
int N;
int map[2100][2100];
char s[2100][10];
int dis(char *str1,char *str2)
{
  int ans=0;
  for(int k=0;k<7;k++)
  {
    if(str1[k]!=str2[k])
    ans++;
  }
  return ans;
}
int prime(int v)
{
  int i,j,k,minn,sum=0;
  int lowcost[2100],vis[2100];
  for(i=1;i<=N;i++)
  {
    lowcost[i]=map[v][i];
    vis[i]=0;
  }
  vis[v]=1;
  for(i=2;i<=N;i++)
  {
    minn=100000;
    for(j=1;j<=N;j++)
    {
      if(lowcost[j]<minn&&!vis[j])
      minn=lowcost[j],k=j;
    }
    sum+=minn,vis[k]=1;
    for(j=1;j<=N;j++)
    {
      if(lowcost[j]>map[k][j]&&!vis[j])
      lowcost[j]=map[k][j];
    }
  }
  return sum;
}
int main()
{
  int i,j,k,g,len1,len2,high;
  while(scanf("%d",&N)!=EOF)
  {
    if(N==0)  break;
    for(i=0;i<N;i++)
    scanf("%s",s[i]);
    for(i=0;i<N;i++)
    {
      for(j=0;j<N;j++)
      {
        if(i!=j)
        map[j+1][i+1]=map[i+1][j+1]=dis(s[i],s[j]);
        else
        map[i+1][j+1]=100000;
      }
    }
    high=prime(1);
    /*for(i=1;i<=N;i++)
    {
      for(j=1;j<=N;j++)
      printf("%d ",map[i][j]);
      cout<<endl;
    }*/
    printf("The highest possible quality is 1/%d.\n",high);
    //system("pause");
  }
}