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 哦