- 问题描述
给省队选拔赛命题的时候，李老师手下有N个命题人，要命N种不同类型的试题，其中每人命一题。因为每个命题人对不同题型的掌握程度不同，所以他们编出的试题难度也有不同（这用一个难度数值来表示）。为了尽可能地刁难大家，李老师决定出一张N个题的试卷，而且所有题的难度值总和最大。
- 输入数据
第一行为N(N <= 100)，代表命题人的个数。
以后N行，每行N个整数（每个数不超过100），第i行j列的数表示第i个人出的第j种题目的难度大小。
- 输出数据
一行，表示试卷难度的最大值。
- 样例输入
3
50 50 1
10 100 10
100 10 10
- 样例输出
201
题解运用最大流
S——N个人——N题——T
S出发 和 会聚到T 的流量无限好理解
中间运用2个权值，一个是难度，一个是1
1是用来确保1人一题不多不少
整体思路如此，希望能注释下程序，越详细越好
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: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(a[i,j].w);
a[i,j].c:=1;
a[j,i].w:=-a[i,j].w;
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
fillchar(best,sizeof(best),0);
best[s].value:=1;
repeat
quit:=true;
for i:=1 to 2*n+2 do
if best[i].value>0 then
for j:=1 to 2*n+2 do
if (a[i,j].f<a[i,j].c) then
if best[i].value+a[i,j].w>best[j].value then begin
best[j].value:=best[i].value+a[i,j].w;
best[j].fa:=i;
quit:=false;
end;
until quit;
if best[t].value>1 then find:=true else find:=false;
end;
procedure add;
var i,j:integer;
begin
i:=t;
while i<>s do begin
j:=best[i].fa;
inc(a[j,i].f);
a[i,j].f:=-a[j,i].f;
i:=j
end;
inc(maxwork,best[t].value-1);
end;
begin
init;
while find do add;
writeln(maxwork);
end.