POJ/1789.pas

   1 const
   2   maxn=2000;
   3
   4 var
   5   adj:array [0..maxn,0..maxn] of longint;
   6   st:array [0..maxn] of string;
   7   dis:array [0..maxn] of longint;
   8   vis:array [0..maxn] of boolean;
   9   i,j,k,n,ans:longint;
  10
  11 begin
  12   readln(n);
  13   while n>0 do
  14     begin
  15       fillchar(adj,sizeof(adj),0);
  16       for i:=1 to n do
  17         begin
  18           readln(st[i]);
  19           for j:=1 to i do
  20             begin
  21               for k:=1 to 7 do
  22                 if st[i][k]<>st[j][k] then inc(adj[i,j]);
  23               adj[j,i]:=adj[i,j];
  24             end;
  25         end;
  26       fillchar(dis,sizeof(dis),$3F);
  27       fillchar(vis,sizeof(vis),false);
  28       ans:=0;
  29       dis[1]:=0;
  30       for i:=1 to n do
  31         begin
  32           k:=0;
  33           for j:=1 to n do
  34             if (not vis[j]) and ((k=0) or (dis[j]<dis[k])) then k:=j;
  35           vis[k]:=true;
  36           inc(ans,dis[k]);
  37           dis[k]:=0;
  38           for j:=1 to n do
  39             if adj[k,j]<dis[j] then dis[j]:=adj[k,j];
  40         end;
  41       writeln('The highest possible quality is 1/',ans,'.');
  42       readln(n);
  43     end;
  44 end.