#include<iostream>
using namespace std;
#define MAXN 2000
struct Edge
{
int u;
int v;
int weight;
};
struct GraphMatrix
{
int adj[MAXN+1][MAXN+1];
};
char str[MAXN+1][8];
GraphMatrix GM;
Edge MST[MAXN+1];
void Prim(GraphMatrix & GM,Edge MST[],int n)
{
int i,j,k;
int si,mi,ni,res;
si=0;
for(i=0;i<n-1;i++)
{
MST[i].u=si;
MST[i].v=i+1;
MST[i].weight=GM.adj[si][i+1];
}
for(i=0;i<n-1;i++)
{
//mi=FindMinEdge(MST,si);
mi=si;
res=100;
for(j=si;j<n-1;j++)
{
if(MST[j].weight>0 && MST[j].weight<res)
{
res=MST[j].weight;
mi=j;
}
}
//swap
Edge tmp;
tmp=MST[mi];
MST[mi]=MST[si];
MST[si]=tmp;
//si++
si++;
//adjust
ni=MST[si-1].v;
for(j=si;j<n-1;j++)
{
k=MST[j].v;
if(GM.adj[ni][k]>0 && GM.adj[ni][k]<MST[j].weight)
{
MST[j].weight=GM.adj[ni][k];
MST[j].u=ni;
}
}
}
}
int main()
{
int n,i,j,k,Q,tmp;
while(scanf("%d",&n)==1 && n!=0)
{
for(i=0;i<n;i++)
scanf("%s",str+i);
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
tmp=0;
for(k=0;k<7;k++)
if(str[i][k]!=str[j][k])
tmp++;
GM.adj[i][j]=GM.adj[j][i]=tmp;
}
Prim(GM,MST,n);
Q=0;
for(i=0;i<n-1;i++)
Q+=MST[i].weight;
printf("The highest possible quality is 1/%d.\n",Q);
}
return 0;
}posted on 2009-07-12 11:54
wyiu 閱讀(133)
評論(0) 編輯 收藏 引用 所屬分類:
POJ