POJ 1273 — Drainage Ditches
有史以来做的第一道网络流的题目…
用了Dinic,果然好写.
原来HopCroft就是简化版的Dinic,有了以前HopCroft的经验,Dinic写起来也就方便的多了.
这道题是裸的网络流,1号节点是源,n号是汇,只要流一下就可以了.
1Y掉,Dinic果然很猛.
附代码,以后Dinic用这个代码套~
{
Drainage Ditches; poj 1273
- sqybi’s code
- 最大流
- Dinic
}
//for my winsty
program pku1273_sqybi;
const
nn = 200;
mm = 200;
type
arr = array[1..nn]of longint;
var
n, m, i, x, y, z, s, t, r: longint;
head, place, dist: arr;
adj, next, f, c: array[-mm..mm]of longint;
function bfs: boolean;
var
q: array[1..nn]of longint;
v: array[1..nn]of boolean;
qs, qe, r, temp: longint;
begin
fillchar(dist, sizeof(dist), 0);
q[1] := s;
qs := 1;
qe := 1;
fillchar(v, sizeof(v), false);
v[s] := true;
while qs <= qe do begin
r := q[qs];
temp := head[r];
while temp <> 0 do begin
if (not v[adj[temp]]) and (f[temp] < c[temp]) then begin
v[adj[temp]] := true;
inc(qe);
q[qe] := adj[temp];
dist[adj[temp]] := dist[r] + 1;
end;
temp := next[temp];
end;
inc(qs);
end;
bfs := dist[t] <> 0;
end;
function min(x, y: longint): longint; inline;
begin
if x < y then
min := x
else
min := y;
end;
function dfs(x, d: longint): longint;
var
temp, delta, r: longint;
begin
if x = t then begin
dfs := d;
exit;
end;
temp := place[x];
delta := 0;
while temp <> 0 do begin
if (dist[adj[temp]] = dist[x] + 1) and (f[temp] < c[temp]) then begin
r := dfs(adj[temp], min(d-delta, c[temp]-f[temp]));
f[temp] := f[temp] + r;
f[-temp] := -f[temp];
delta := delta + r;
if delta = d then break;
end;
temp := next[temp];
end;
place[x] := temp;
dfs := delta;
end;
begin
repeat
fillchar(head, sizeof(head), 0);
readln(m, n);
for i:=1 to m do begin
readln(x, y, z);
adj[i] := y;
c[i] := z;
f[i] := 0;
adj[-i] := x;
c[-i] := 0;
f[-i] := 0;
next[i] := head[x];
head[x] := i;
next[-i] := head[y];
head[y] := -i;
end;
s := 1;
t := n;
r := 0;
while bfs do begin
place := head;
r := r + dfs(s, maxlongint);
end;
writeln(r);
until seekEoF;
end.
阅读(280 次)