最小费用最大流方法: program work;
const maxn=100;
type node1=record
w,f,c:integer
end;
type node2=record
value:integer;
fa:integer;
end;
var a:array[1..maxn+2,1..maxn+2] of node1;
best:array[1..maxn+2] of node2;
n,maxwork,s,t:integer;
procedure init;
var i,j,x:integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
for j:=n+1 to 2*n do
begin
read(x);
a[i,j].c:=1;
a[i,j].w:=-x;
a[j,i].w:=x;
end;
s:=2*n+1;
t:=2*n+2;
for i:=1 to n do
begin
a[s,i].c:=1;
a[n+i,t].c:=1;
end;
maxwork:=0;
end;
function find:boolean;
var i,j:integer;
quit:boolean;
begin
for i:=1 to 2*n+2 do best.value:=maxint;
best.value:=0;
repeat
quit:=true;
for i:=1 to 2*n+2 do
if best.value<>maxint then
for j:=1 to 2*n+2 do
if (a[i,j].f<a[i,j].c) then
if best.value+a[i,j].w<best[j].value then
begin
best[j].value:=best.value+a[i,j].w;
best[j].fa:=i;
quit:=false;
end;
until quit;
if best[t].value<maxint then find:=true else find:=false;
end;
procedure add;
var i,j:integer;
begin
i:=t;
while i<>s do
begin
j:=best.fa;
inc(a[j,i].f);
a[i,j].f:=-a[j,i].f;
i:=j
end;
inc(maxwork,best[t].value);
end;
begin
init;
while find do add;
writeln(-maxwork);
end.
|