这题 居然一次就过了^_^
Program P2195;
const
maxn=200;
maxm=200;
maxh=200;
maxd=1000;
var
n,m,i,j,k,ut,vt:longint;
s:string;
form:array[1..maxn,1..maxm] of longint;
u,v:array[1..maxh,1..2] of longint;
map,f,cost:array[0..maxd,0..maxd] of longint;
b:array[0..maxd] of boolean;
q:array[1..maxd*5] of longint;
d,pre:array[0..maxd] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure spfa;
var
i,j,h,t,now:longint;
begin
fillchar(d,sizeof(d),127);
fillchar(b,sizeof(b),false);
fillchar(pre,sizeof(pre),0);
d[0]:=0;
b[0]:=true;
h:=1;t:=1;
q[1]:=0;
while h<=t do
begin
now:=q[h];
for i:=0 to 2*ut+1 do
if (map[now,i]-f[now,i]>0) then
if (d[now]+cost[now,i]<d[i]) then
begin
d[i]:=d[now]+cost[now,i];
pre[i]:=now;
if not(b[i]) then
begin
b[i]:=true;
inc(t);
q[t]:=i;
end;
end;
b[now]:=false;
inc(h);
end;
end;
function hllp:longint;
var
i,j,k,flow,totalcost,nowcost:longint;
begin
hllp:=0;
totalcost:=0;
while (true) do
begin
spfa;
if d[ut*2+1]=2139062143 then exit(totalcost);
flow:=maxlongint;
i:=ut*2+1;
repeat
flow:=min(map[pre[i],i]-f[pre[i],i],flow);
i:=pre[i];
until i=0;
i:=ut*2+1;
nowcost:=0;
repeat
inc(f[pre[i],i],flow);
f[i,pre[i]]:=-f[pre[i],i];
inc(nowcost,cost[pre[i],i]);
i:=pre[i];
until i=0;
inc(totalcost,nowcost*flow);
end;
end;
function main:longint;
var
i,j,k:longint;
begin
main:=0;
fillchar(map,sizeof(map),0);
fillchar(f,sizeof(f),0);
fillchar(cost,sizeof(cost),0);
for i:=1 to ut do map[0,i]:=1;
for i:=ut+1 to ut+vt do map[i,ut+vt+1]:=1;
for i:=1 to ut do
for j:=ut+1 to ut+vt do
begin
map[i,j]:=1;
cost[i,j]:=abs(u[i,1]-v[j-ut,1])+abs(u[i,2]-v[j-ut,2]);
cost[j,i]:=-cost[i,j];
end;
main:=hllp;
end;
begin
while not eof do
begin
readln(n,m);
if (n=0) and (m=0) then break;
ut:=0;
vt:=0;
for i:=1 to n do
begin
readln(s);
for j:=1 to m do
if s[j]='m' then
begin
inc(ut);
u[ut,1]:=i;
u[ut,2]:=j;
end
else if s[j]='H' then
begin
inc(vt);
v[vt,1]:=i;
v[vt,2]:=j;
end;
end;
writeln(main);
end;
end.
分享到:
相关推荐
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
poj2516代码最小费用最大流
这是北京大学ACM也就是POJ2195的源代码,用的是最优匹配算法。
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj2823 最大最小堆实现,话说这题为啥要用最大最小堆。
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码