讨论 / 求教~
love_hcy 2008-07-14 22:58:00
点我顶贴 收藏 删除
因为流网络是有向图,那么在枚举汇点时,如何将无向图转换成流网络?
#1 love_hcy@2008-07-14 02:58:00
回复 删除
没人理啊..

没人理也要顶起~

#2 wish@2008-07-14 22:57:00
回复 删除
两个方向的容量都设置就好了

这题不难的 ^_^

#3 wish@2008-07-14 22:58:00
回复 删除
program p77(input, output);

var

ch: char;

n, t, oldheight, sum, mininum, i, j: longint;

e, h: array [1..50] of longint;

f, c: array [1..50, 1..50] of longint;

L: array [1..50, 0..50] of longint;

List: array [0..1000] of longint;

function min(a, b: longint): longint;

begin

if a > b then

exit(b)

else

exit(a)

end;

procedure push(u, v: longint);

var

d: longint;

begin

d := min(e[u], c[u, v] - f[u, v]);

inc(f[u, v], d);

f[v, u] := - f[u, v];

dec(e[u], d);

inc(e[v], d)

end;

procedure relabel(u: longint);

var

i, t: longint;

begin

t := maxlongint;

for i := 1 to n do

if c[u, i] - f[u, i] > 0 then

t := min(t, h[i]);

h[u] := t + 1

end;

procedure discharge(u: longint);

var

i, v: longint;

begin

i := 1;

while e[u] > 0 do

begin

if i > L[u, 0] then

begin

relabel(u);

i := 1

end

else

begin

v := L[u, i];

if (c[u, v] - f[u, v] > 0) and (h[u] = h[v] + 1) then

push(u, v)

else

inc(i)

end

end

end;

procedure initialize;

var

g: longint;

begin

fillchar(e, sizeof(e), 0);

fillchar(h, sizeof(h), 0);

fillchar(f, sizeof(f), 0);

fillchar(List, sizeof(List), 0);

h[1] := n;

for i := 1 to n do

if c[1, i] > 0 then

begin

f[1, i] := c[1, i];

f[i, 1] := - c[1, i];

e[i] := c[1, i];

dec(e[1], e[i])

end;

g := 0;

for i := 2 to n do

if i <> t then

begin

inc(g);

List[g] := i

end

end;

procedure dmove(pos: longint);

var

i, t: longint;

begin

t := List[pos];

for i := pos downto 2 do

List[i] := List[i - 1];

List[1] := t

end;

begin

fillchar(L, sizeof(L), 0);

readln(n);

for i := 1 to n do

begin

for j := 1 to n do

begin

read(ch);

c[i, j] := ord(ch) - ord(0);

if c[i, j] > 0 then

begin

inc(L[i, 0]);

L[i, L[i, 0]] := j

end

end;

readln

end;

mininum := maxlongint;

for t := 2 to n do

begin

initialize;

j := 1;

while j <= n - 2 do

begin

oldheight := h[List[j]];

discharge(List[j]);

if h[List[j]] > oldheight then

begin

dmove(j);

j := 2

end

else

inc(j)

end;

sum := 0;

for j := 1 to n do

inc(sum, f[j, t]);

mininum := min(mininum, sum)

end;

writeln(mininum)

end.

这是我的程序

大家不要随便 copy 哦

查看更多回复
提交回复