TOI 1116 — 运送物资
又是KM的题目.对任意一对仓库和物资之间以距离的相反数为权值建边,然后KM.注意权值为负是因为需要求带权最小匹配.
写的依然不熟,很诧异自己当时写了一次KM就一直没动过…忘得死死的.
还好还有时间,最近复习好KM和HopCroft.似乎Dinic没法代替HopCroft…
{
TOI 1116; 运送物资
- sqybi’s code
- 带权最小匹配
- KM
}
program toi1116_sqybi;
const
fin = ’snow.in’;
fout = ’snow.out’;
nn = 100;
var
n, m, nx, ny, i, j, r: longint;
ch: char;
x, y: array[1..nn, 0..1]of longint;
d: array[1..nn, 1..nn]of longint;
match, lx, ly: array[1..nn]of longint;
vx, vy: array[1..nn]of boolean;
function search(x: longint): boolean;
var
i, t: longint;
begin
search := false;
if vx[x] then exit;
vx[x] := true;
search := true;
for i:=1 to ny do
if (not vy[i]) and (lx[x] + ly[i] = d[x, i]) then begin
vy[i] := true;
t := match[i];
match[i] := x;
if (t = 0) or search(t) then exit;
match[i] := t;
end;
search := false;
end;
procedure km;
var
i, j, k, delta: longint;
begin
fillchar(match, sizeof(match), 0);
for i:=1 to nx do
for j:=1 to ny do
if (d[i, j] > lx[i]) or (lx[i] = 0) then
lx[i] := d[i, j];
for i:=1 to nx do
repeat
fillchar(vx, sizeof(vx), false);
fillchar(vy, sizeof(vy), false);
if search(i) then break;
delta := maxlongint;
for j:=1 to nx do
if vx[j] then
for k:=1 to ny do
if not vy[k] then
if lx[j] + ly[k] - d[j, k] < delta then
delta := lx[j] + ly[k] - d[j, k];
for j:=1 to nx do
if vx[j] then
lx[j] := lx[j] - delta;
for j:=1 to ny do
if vy[j] then
ly[j] := ly[j] + delta;
until false;
end;
begin
assign(input, fin);
assign(output, fout);
reset(input);
rewrite(output);
readln(n, m);
nx := 0; //m
ny := 0; //H
for i:=1 to n do begin
for j:=1 to m do begin
read(ch);
if ch = ‘m’ then begin
inc(nx);
x[nx, 0] := i;
x[nx, 1] := j;
end
else if ch = ‘H’ then begin
inc(ny);
y[ny, 0] := i;
y[ny, 1] := j;
end;
end;
readln;
end;
for i:=1 to nx do
for j:=1 to ny do
d[i, j] := - abs(y[j, 0]-x[i, 0]) - abs(y[j, 1]-x[i, 1]);
km;
r := 0;
for i:=1 to ny do
r := r - d[match[i], i];
writeln(r);
close(input);
close(output);
end.
阅读(99 次)