题目：http://acm.hdu.edu.cn/showproblem.php?pid=1533
关于KM的简单讲解&&模板 推荐（写的很详细也很容易理解）：http://blog.csdn.net/pi9nc/article/details/12250247
题目求最小权值和，KM处理的是最大权值和，在建图的时候每条边建成负数即可
第一次写KM匹配，代码改得比较丑
type rec=record xx,yy:longint; end; var n,m,t1,t2 :longint; i,j :longint; s :string; visx,visy :array[0..10010] of boolean; link,lx,ly :array[0..10010] of longint; x,y :array[0..10010] of rec; map :array[0..110,0..110] of longint; function find(x:longint):boolean; var i:longint; begin visx[x]:=true; for i:=1 to t2 do if not visy[i] and (map[x,i]<>0) and (lx[x]+ly[i]=map[x,i]) then begin visy[i]:=true; if (link[i]=0) or (find(link[i])) then begin link[i]:=x; exit(true); end; end; exit(false); end; procedure KM(n,m:longint); var i,j,k:longint; ans,tt:longint; begin for i:=1 to n do begin ly[i]:=0; lx[i]:=-maxlongint; for j:=1 to m do if (map[i,j]<>0) and (map[i,j]>lx[i]) then lx[i]:=map[i,j]; end; // fillchar(link,sizeof(link),0); for i:=1 to n do begin while true do begin fillchar(visx,sizeof(visx),false); fillchar(visy,sizeof(visy),false); if find(i) then break; // tt:=maxlongint; for j:=1 to n do if visx[j] then for k:=1 to m do if not visy[k] and (map[j,k]<>0) and (lx[j]+ly[k]-map[j,k]<tt) then tt:=lx[j]+ly[k]-map[j,k]; // for j:=1 to n do begin if visx[j] then dec(lx[j],tt); if visy[j] then inc(ly[j],tt); end; end; end; // ans:=0; for i:=1 to m do if link[i]>0 then inc(ans,map[link[i],i]); writeln(-ans); end; begin read(n,m); while(n<>0) and (m<>0) do begin readln; t1:=0; t2:=0; fillchar(map,sizeof(map),0); for i:=1 to n do begin readln(s); for j:=1 to m do if s[j]='H' then begin inc(t1); x[t1].xx:=i; x[t1].yy:=j; end else if s[j]='m' then begin inc(t2); y[t2].xx:=i; y[t2].yy:=j; end; end; // for i:=1 to t1 do for j:=1 to t2 do map[i,j]:=-abs(x[i].xx-y[j].xx)-abs(x[i].yy-y[j].yy); // KM(t1,t2); read(n,m); end; end. ——by Eirlys
