#include<iostream>
using namespace std;
#define maxn 2001
int cost[maxn];//记录权值的数组
int used[maxn];//判断点是否访问过
int graph[maxn][maxn];
char s[maxn][8];
int n;
int solve()//用prime算法的函数
{
int legth = 0;//总权值
for(int ix = 0; ix < n; ix++)
{
cost[ix] = graph[0][ix];
used[ix] = 0;
}
used[0] = 1;
for(;;)
{
int j = 0, i = 0;
while(used[j] && j < n)
j++;//找一个没访问的点
if(j == n) break;//如果都访问过了，跳出循环
for(i = 0; i < n; i++)
if(!used[i] && cost[i] < cost[j])
j = i;//在剩下的点中找到权值最小的点（权值
//是指起始点到此点的路径长度）
legth += cost[j];//更新总权值
used[j] =1;//将此点置为访问过
for(i = 0; i < n; i++)
if(!used[i] && graph[j][i] < cost[i])
cost[i] = graph[j][i];//更新未访问的所有点的权值
}
// printf("%d\n",legth);
return legth;
}
int main()
{
int i,j,sum;
while(cin>>n){
if( n == 0)break;
for( i=0;i<=n;i++){used[i]=0;cost[i]=0;}
for(i=0;i<n;i++ ){
cin>>s[i];
}
for( i=0;i<n;i++)
for( j=0;j<n;j++){
if( i == j)graph[i][j]=0;
else {
sum=0;
for( int k=0;k<7;k++){
if(s[i][k]!=s[j][k])sum++;
}
graph[i][j]=sum;
}
}
cout<<"The highest possible quality is 1/"<<solve()<<"."<<endl;
}
//system("pause");
return 0;
}
今天第一个一ac的题目
晕死
用prim做的
那天，我可以得心应手的 一ac这些简单题啊
加油！傻傻地贴这些无聊的东西。
外卖仔还没送饭来！！
wait。。。。。。。。
posted on 2008-10-11 16:58
爬 阅读(1266)
评论(0) 编辑 收藏 引用 所属分类:
pku