题目链接：
POJ 1789 Truck History
题意：
n个7个字符串的点，两点之间的权值是两个字符串相同位置上相异字符数。
由于要求的是把这n个点连通1/权值和的最大值，所以也就是求权值和的最小值（最小生成树）
分析：
Prim算法。两点间权值按照题意自己建立然后套用模版就行了。
CODE:
//16196K 485MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=2010;
const int INF=0x3f3f3f3f;int n,st,k,mindis;
int ans,map[maxn][maxn],dis[maxn],vis[maxn];
char s[maxn][10];int calc(char s1[10],char s2[10])
{int tmp=0;for(int i=0;i<7;i++)if(s1[i]!=s2[i]) tmp++;return tmp;
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifwhile(~scanf("%d",&n)&&n){for(int i=1;i<=n;i++)scanf("%s",s[i]);for(int i=1;i<=n;i++){map[i][i]=0;for(int j=i+1;j<=n;j++){map[i][j]=map[j][i]=calc(s[i],s[j]);}}//Prim Algorithmans=0;memset(vis,0,sizeof(vis));st=1;vis[st]=1;//记录开始点,开始点可以任意选择for(int i=1;i<=n;i++)dis[i]=map[st][i];for(int i=1;i<n;i++)//运行n-1次，每次添加一个顶点{mindis=INF;k=-1;for(int j=1;j<=n;j++)//从未连通点中找到权值最小的点{if(!vis[j]&&dis[j]<mindis){mindis=dis[j];k=j;}}vis[k]=1;//标记已连通ans+=mindis;//权值累加for(int j=1;j<=n;j++)//更新权值{if(!vis[j]&&dis[j]>map[k][j])dis[j]=map[k][j];}}printf("The highest possible quality is 1/%d.\n",ans);}return 0;
}