poj1789--最小生成树(prim)

时间:2023-03-09 17:33:07
poj1789--最小生成树(prim)

水题。。。

题目大意:

用一个7位的字符串代表一个编号,两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来,代价是这两个编号之间相应的distance,现在要找出一个“衍生”方案,使得总代价最小,也就是distance之和最小。

很容易想到,将每两个顶点间的distance求出作为边权,将题目转化为最小生成树问题。由于是稠密图,所以用prim算法。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,k,n,m,x,a[][],ans,minn,d[],tot,c[];
bool b[];
char s[][];
int main()
{
scanf("%d",&n);
while(n){
memset(d,,sizeof(d));
memset(b,,sizeof(b));
memset(a,,sizeof(a));
ans=;tot=;
for(i=;i<=n;i++)scanf("%s",s[i]);
for(i=;i<n;i++)
for(j=i+;j<=n;j++){
for(k=;k<;k++)if(s[i][k]!=s[j][k])a[i][j]++;
a[j][i]=a[i][j];
}
c[]=;d[]=;k=;b[]=;
while(tot<n){
minn=;
for(i=;i<=n;i++)
if(!b[i]){
if(d[c[k]]+a[c[k]][i]<d[i])d[i]=d[c[k]]+a[c[k]][i];
if(d[i]<minn){
minn=d[i];
x=i;
}
}
b[x]=;
c[++tot]=x;
ans+=d[x];
d[x]=;
k++;
}
printf("The highest possible quality is 1/%d.\n",ans);
scanf("%d",&n);
}
return ;
}