SPOJ 371 — Boxes (code: BOXES)
一道很经典的费用流题目,也是第一次写费用流.SPFA写错了一点.另外终于理解上次SGU那道题为啥可以用费用流了…
题目描述懒得写了…
建图的方法:
s到每个盒子连边,容量为盒子里球的数量,费用0.
盒子到t连边,容量为1,费用0.
相邻的两个盒子连边,容量为正无穷,费用1.
要求的就是最小费用.
{
SPOJ 371; BOXES
- sqybi’s code
- 最小费用最大流
}
//for my winsty
program boxes_sqybi;
const
nn = 1000;
inf = 100000000;
mm = nn * 4;
tt = nn + 2;
var
cases, times, n, m, s, t, i, x, y, qs, ql, temp, now, res: longint;
head, dist, go, path, pathEdge: array[1..tt]of longint;
q: array[0..tt-1]of longint;
flag: array[1..tt]of boolean;
flow, next, adj, w, capa: array[-mm..mm]of longint;
procedure addEdge(x, y, c, z: longint);
begin
inc(m);
adj[m] := y;
capa[m] := c;
w[m] := z;
flow[m] := 0;
next[m] := head[x];
head[x] := m;
adj[-m] := x;
capa[-m] := 0;
w[-m] := -z;
flow[-m] := 0;
next[-m] := head[y];
head[y] := -m;
end;
function min(x, y: longint): longint;
begin
if x < y then min := x else min := y;
end;
begin
readln(cases);
for times:=1 to cases do begin
readln(n);
s := 1;
t := n + 2;
m := 0;
fillchar(head, sizeof(head), 0);
for i:=2 to n+1 do begin
read(x);
addEdge(s, i, x, 0);
y := i - 1;
if y = 1 then y := n + 1;
addEdge(i, y, inf, 1);
y := i + 1;
if y = n + 2 then y := 2;
addEdge(i, y, inf, 1);
addEdge(i, t, 1, 0);
end;
readln;
repeat
for i:=s+1 to t do dist[i] := inf;
dist[s] := 0;
fillchar(go, sizeof(go), 0);
go[s] := inf;
qs := 0;
ql := 1;
q[0] := s;
fillchar(flag, sizeof(flag), true);
flag[s] := false;
while ql <> 0 do begin
now := q[qs];
temp := head[now];
while temp <> 0 do begin
if (flow[temp] < capa[temp]) and (dist[now] + w[temp] < dist[adj[temp]]) then begin
dist[adj[temp]] := dist[now] + w[temp];
go[adj[temp]] := min(go[now], capa[temp]-flow[temp]);
path[adj[temp]] := now;
pathEdge[adj[temp]] := temp;
inc(ql);
q[(qs+ql-1) mod t] := adj[temp];
flag[adj[temp]] := false;
end;
temp := next[temp];
end;
flag[now] := true;
qs := (qs + 1) mod t;
dec(ql);
end;
if dist[t] = inf then break;
now := t;
while now <> s do begin
flow[pathEdge[now]] := flow[pathEdge[now]] + go[t];
flow[-pathEdge[now]] := - flow[pathEdge[now]];
now := path[now];
end;
until false;
res := 0;
for i:=1 to m do
res := res + flow[i] * w[i];
writeln(res);
end;
end.
阅读(6 次)
Read Full Post | Make a Comment ( None so far )