#include<iostream>
using namespace std;
#define maxn 2001
int cost[maxn];//記錄權(quán)值的數(shù)組
int used[maxn];//判斷點(diǎn)是否訪問過
int graph[maxn][maxn];
char s[maxn][8];
int n;
int solve()//用prime算法的函數(shù)
{
int legth = 0;//總權(quán)值
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++;//找一個沒訪問的點(diǎn)
if(j == n) break;//如果都訪問過了，跳出循環(huán)
for(i = 0; i < n; i++)
if(!used[i] && cost[i] < cost[j])
j = i;//在剩下的點(diǎn)中找到權(quán)值最小的點(diǎn)（權(quán)值
//是指起始點(diǎn)到此點(diǎn)的路徑長度）
legth += cost[j];//更新總權(quán)值
used[j] =1;//將此點(diǎn)置為訪問過
for(i = 0; i < n; i++)
if(!used[i] && graph[j][i] < cost[i])
cost[i] = graph[j][i];//更新未訪問的所有點(diǎn)的權(quán)值
}
// 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做的
那天，我可以得心應(yīng)手的 一ac這些簡單題啊
加油！傻傻地貼這些無聊的東西。
外賣仔還沒送飯來！！
wait。。。。。。。。
posted on 2008-10-11 16:58
爬 閱讀(1276)
評論(0) 編輯 收藏 引用 所屬分類:
pku