poj 1789

题意：历史上，曾用7个小写字母来表示每种truck的型号，每两种型号之间的差距为字母串中不同字母的个数。现在给出n种不同型号的truck，问怎样使

1/Σ_(to,td)d(t_o,t_d)的值最小。（即找到一条连接所有truck的最短路径。典型的最小生成树的问题， discuss里说，Prim算法适合稠密图，Kruskal算法适合稀疏图，可以使用prim和kruskal两种方法。该题是稠密的图。求最小生成树的最段路径问题：

不说了 直接看代码：

#include <iostream>
using namespace std;
const int Max=2005;
const int inf=0xfffff;

int n,ans;
int map[Max][Max],dis[Max];

int min(int a,int b)
{
	return a<b?a:b;
}

void prim()
{
    int i, j, now, min_node, min_edge;
    for(i = 1; i <= n; i ++)
        dis[i] = inf;
    now = 1;
    ans = 0;
    for(i = 1; i < n; i ++)
	{
        dis[now] = -1;
        min_edge = inf;
        for(j = 1; j <= n; j ++)
            if(j != now && dis[j] >= 0)
			{
                dis[j] = min(dis[j], map[now][j]);
                if(dis[j] < min_edge)
				{
                    min_edge = dis[j];
                    min_node = j;
                }
            }
			now = min_node;
			ans += min_edge;
    }
}

int main()
{
	int i,j,k;
	char truck[Max][8];
	while (cin>>n&&n!=0)
	{
		for (i=1;i<=n;i++)
		{
			scanf("%s",&truck[i]);
			for (j=i-1;j>=1;j--)
			{
				int edge=0;
				for(k=0;k<7;k++)
					if(truck[i][k]!=truck[j][k])
						edge++;
					map[i][j]=map[j][i]=edge;

			}
		}
		prim();
		printf("The highest possible quality is 1/%d.\n", ans);
	}
	return 0;
}

 具体的prim模板参见前几题，关于最小生成树问题，未完待续……