POJ 1789 Truck History：最小生成树 Prim

POJ 1789 Truck History：最小生成树 Prim2015-02-25Truck History：http://poj.org/problem？id=1789

大意：用一个7位的string代表一个编号，两个编号之间的距离代表这两个编号之间不同字母的个数。一个编号只能由另一个编号变化的来，变化的字母的数量就是这两个编号之间相应的距离，现在要找出一个变化方案，使得总代价最小，也就是距离之和最小。

思路：将每个字符串当成一个节点，求出每个节点之间需要变化的次数为边的权值，用Prim建立最小生成树（稠密图）。

#include <stdio.h>#include <string.h>#define INF 0x3f3f3f3fint Map[2010][2010];char s[2010][8];int dis[2010];int n;int min（int a, int b）{return a > b ？ b : a;}int length（int i, int j）{int cnt = 0;for（int k = 0; k < 7; k++）{if（s[i][k] ！= s[j][k]）cnt++;}return cnt;}int Prim（）{int Ans;int Min_ele, Min_node;memset（dis, INF, sizeof（dis））;Ans = 0;int r = 1;for（int i = 1; i <= n-1; i++）{Min_ele = INF;dis[r] = -1;for（int j = 1; j <= n; j++）{if（dis[j] >= 0）{dis[j] = min（dis[j], Map[r][j]）;if（dis[j] < Min_ele）{Min_ele = dis[j];Min_node = j;}}}r = Min_node;Ans += Min_ele;}return Ans;}void Solve（）{while（~scanf（"%d%*c", &n） && n）{for（int i = 1; i <= n; i++）{scanf（"%s", s[i]）;}memset（Map, 0, sizeof（Map））;for（int i = 1; i <= n-1; i++）{for（int j = i+1; j <= n; j++）{Map[i][j] = Map[j][i] = length（i, j）;}}printf（"The highest possible quality is 1/%d.
", Prim（））;}}int main（）{Solve（）;return 0;}

From：cnblogs GLsilence