#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
爬 閱讀(1282)
評論(0) 編輯 收藏 引用 所屬分類:
pku