ac1148.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1148;
const
  maxn=20;
var
  w:array[1..maxn,1..maxn]of byte;
  m,lx,ly:array[1..maxn]of byte;
  vx,vy:array[1..maxn]of boolean;
  n,i,j,k,d,ans:word;
function find(x:byte):boolean;
  var
    y:byte;
  begin
    find:=false;
    vx[x]:=true;
    for y:=1 to n do
      if not vy[y] and (lx[x]+ly[y]=w[x,y]) then begin
        vy[y]:=true;
        if (m[y]=0) or find(m[y]) then begin
          m[y]:=x;find:=true;exit;
        end;
      end;
  end;
begin
  repeat
    read(n);
    if n=0 then halt;
    fillchar(m,sizeof(m),0);
    fillchar(lx,sizeof(lx),0);
    fillchar(ly,sizeof(ly),0);
    for i:=1 to n do
      for j:=1 to n do begin
        read(w[i,j]);
        if w[i,j]>lx[i] then lx[i]:=w[i,j];
      end;

    for k:=1 to n do
      repeat
        fillchar(vx,sizeof(vx),0);
        fillchar(vy,sizeof(vy),0);
        if find(k) then break;
        d:=255;
        for i:=1 to n do
          if vx[i] then
            for j:=1 to n do
              if not vy[j] then
                if lx[i]+ly[j]-w[i,j]<d then
                  d:=lx[i]+ly[j]-w[i,j];
        for i:=1 to n do begin
          if vx[i] then dec(lx[i],d);
          if vy[i] then inc(ly[i],d);
        end;
      until false;

    ans:=0;
    for i:=1 to n do
      inc(ans,w[m[i],i]);
    writeln(ans);
  until seekeof;
end.