POJ1789-Truck History .

題目鏈接：http://poj.org/problem?id=1789
題目的大概意思就是給你n個字符串。每個字符串只有7的長度。然后分別給這些字符串編號。不同編號之間的距離就是他們有多少個不同的字母。（同一個位置字母不相同也算）然后一個編號只能由另一個派生出來。派生的代價就是他們呢之間的距離。現在要你求最小的總代價。
編號的范圍是2-2000.屬于稠密圖。求最小生成樹最好用prim算法。用克魯斯卡爾會可能會超時。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2220;
int G[N][N];
int low[N],vis[N];
char s[N][10];
int n;
int prim()
{memset(vis,0,sizeof(vis));int  pos=0;int min;int ans=0;vis[0]=1;for(int i=0;i<n;i++)low[i]=G[pos][i];for(int i=0;i<n-1;i++){min=100;for(int j=0;j<n;j++){if(!vis[j]&&low[j]<min){min=low[j];pos=j;}}vis[pos]=1;ans+=min;for(int j=0;j<n;j++){if(!vis[j]&&low[j]>G[pos][j])low[j]=G[pos][j];}}return ans;
}
int main()
{while(scanf("%d",&n)!=EOF&&n){for(int i=0;i<n;i++)scanf("%s",s[i]);int cnt=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){int tmp=0;for(int k=0;k<7;k++){if(s[i][k]!=s[j][k])tmp++;}int u=i;int v=j;G[u][v]=tmp;G[v][u]=tmp;}}int ans=prim();printf("The highest possible quality is 1/%d.\n",ans);  }return 0;
}