[题目来源]：CTU Open 2003
[关键字]：图论
[题目大意]：给出一个n*7的字母矩阵，每一行代表一种车，那么定义的每种车之间的距离为七个位置上每个相应的位置上不同字母数的和，要求的是不同种车的距离的和得最小值。
//=====================================================================================================
[分析]：其实就是最小生成树的算法，由于是稠密图所以prim效率更高。
[代码]：
View Code 1 { 2 PROB:POJ1789 3 DATE:2011\10\14 4 } 5 program project1; 6 var 7 n: longint; 8 w: array[0..2010] of string[7]; 9 map: array[0..2010,0..2010] of byte;10 d: array[0..2010] of longint;11 b: array[0..2011] of boolean;12 13 function dis(s1, s2: string):longint;14 var15 i, sum: longint;16 begin17 sum := 0;18 for i := 1 to 7 do19 if s1[i] <> s2[i] then inc(sum);20 exit(sum);21 end;22 23 procedure init;24 var25 i, j: longint;26 begin27 readln(n);28 if n = 0 then halt;29 for i := 1 to n do30 readln(w[i]);31 for i := 1 to n do32 for j := i+1 to n do33 begin34 map[i,j] := dis(w[i],w[j]);35 map[j,i] := map[i,j];36 end;37 end;38 39 procedure prim;40 var41 i, j, p, ans, min: longint;42 begin43 fillchar(b,sizeof(b),false);44 fillchar(d,sizeof(d),100);45 d[1] := 0;46 ans := 0;47 for i := 1 to n do48 begin49 min := maxlongint;50 for j := 1 to n do51 if (not b[j]) and (min > d[j]) then52 begin53 min := d[j];54 p := j;55 end;56 inc(ans,min);57 b[p] := true;58 for j := 1 to n do59 if (not b[j]) and (d[j] > map[p,j]) then60 d[j] := map[p,j];61 end;62 writeln('The highest possible quality is 1/',ans,'.');63 end;64 65 begin66 while 1 = 1 do67 begin68 init;69 prim;70 end;71 end.转载于:https://www.cnblogs.com/procedure2012/archive/2011/11/02/2232838.html
