给你一个n；
n个长为7的字符串；
每个字符串表示一个节点，每个节点向其他所有点都有边，边长为两个节点字符串同一位置不同字符的数量；
需要你生成最短路的边权和。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define INF 0x3f3f3f3f
int mp[2005][2005];
char str[2005][8];
int n;
void change(){
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int sum=0;
for(int k=0;k<7;k++){
if(str[i][k]!=str[j][k])
sum++;
}
mp[i][j]=mp[j][i]=sum;
}
}
}
int prim(int st){
int vis[2005];
int low[2005];
int mincost=0;
memset(vis,0,sizeof(vis));
vis[st]=1;
for(int i=0;i<n;i++){
low[i]=mp[st][i];
}
low[st]=0;
for(int i=0;i<n-1;i++)
{
int minn=INF;
int u=-1;
for(int j=0;j<n;j++){
if(minn>low[j]&&!vis[j]){
minn=low[j];
u=j;
}
}
if(minn==INF)return -1;
vis[u]=1;
mincost+=minn;
for(int k=0;k<n;k++){
if(!vis[k]&&low[k]>mp[u][k])
{
low[k]=mp[u][k];
}
}
}
return mincost;
}
int main(){
while(scanf("%d",&n)&&n){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
mp[i][j]=(i==j?0:INF);
for(int i=0;i<n;i++){
scanf("%s",str[i]);
}
change();
printf("The highest possible quality is 1/%d.\n",prim(0));
}
return 0;
}
