P1653疯狂的方格取数
背景
Due to the talent of talent123,当talent123做完NOIP考了两次的二取方格数和vijos中的三取方格数后，突发奇想....
描述
在一个宽M，长N的矩阵中，请你编一个程序，n次从矩阵的左上角走到矩阵的右下角，每到一处，就取走该处的数字，请你选择一
种走法使取得的数字的和最大,并输出其最大值。其中：3<=M<=20 M<=N<=100 1<=n<=10
如输入数据：
3 10 13
0 1 2 3 4 9 7 1 3 1
9 1 2 2 3 6 7 8 1 2
1 2 3 4 5 9 8 7 6 1
9 7 1 3 1 9 1 2 2 3
6 7 8 1 2 1 2 3 4 5
9 1 2 2 3 6 7 8 1 2
1 2 3 4 5 9 8 7 6 1
9 7 1 3 1 9 1 2 2 3
6 7 8 1 2 1 2 3 4 5
9 1 2 2 3 6 7 8 1 2
1 2 3 4 5 9 8 7 6 1
9 7 1 3 1 9 1 2 2 3
6 7 8 1 2 1 2 3 4 0
其中n=3
M=10
N=13
即当n=3时，就相当于是3取方格数。
对于以上的数据：
将输出：297
//注：如过你想到了无记忆性搜所的方法（不管你怎样优化），你可以直接放弃这道题了。
//提示1：动态规划如果用的是二位数组，规模为100*100000即可。
//提示2：如果你坚信自己的程序已经无可优化了，可有2个数据依然超时，那么告诉你，存在数据有M<n的情况！！！
格式
输入格式
第一行：三个整数：n M N
以下的N行每行M个数字，代表你要处理的矩阵。
输出格式
只有一行：你所取得的数字的和。
样例1
限制
共有10个测试数据，每个测试数据包含1个测试点，每个测试点的时间限制为2秒钟。
来源
本题目来自：北京市，中关村中学，高三9班，孙一（网名:talent123
题解：
当年的难题如今终于轻松解决了……
不多说了，水题一道……
网络流想几道基本上就差不多了……
最大费用最大流
代码：
方法一：将费用取负
uses math;
const inf=maxlongint;
type node=record
from,go,next,v,c:longint;
end;
var e:array[..] of node;
pre,head,q,d:array[..] of longint;
v:array[..] of boolean;
num:array[..,..] of longint;
i,j,n,s,t,l,r,mincost,tot,k,x,m:longint;
procedure ins(x,y,z,w:longint);
begin
inc(tot);
with e[tot] do
begin
from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot;
end;
end;
procedure insert(x,y,z,w:longint);
begin
if y> then exit;
ins(x,y,z,w);ins(y,x,,-w);
end;
function spfa:boolean;
var i,x,y:longint;
begin
fillchar(v,sizeof(v),false);
for i:=s to t do d[i]:=inf;
l:=;r:=;q[]:=s;d[s]:=;v[s]:=true;
while l<r do
begin
inc(l);
x:=q[l];v[x]:=false;
i:=head[x];
while i<> do
begin
y:=e[i].go;
if (e[i].v<>) and (d[x]+e[i].c<d[y]) then
begin
d[y]:=d[x]+e[i].c;
pre[y]:=i;
if not(v[y]) then
begin
v[y]:=true;
inc(r);
q[r]:=y;
end;
end;
i:=e[i].next;
end;
end;
exit(d[t]<>inf);
end;
procedure mcf;
var i,tmp:longint;
begin
mincost:=;
while spfa do
begin
tmp:=inf;
i:=pre[t];
while i<> do
begin
tmp:=min(tmp,e[i].v);
i:=pre[e[i].from];
end;
inc(mincost,tmp*d[t]);
i:=pre[t];
while i<> do
begin
dec(e[i].v,tmp);
inc(e[i xor ].v,tmp);
i:=pre[e[i].from];
end;
end;
end;
procedure init;
begin
tot:=;
readln(k,m,n);
s:=;t:=*n*m+;
insert(s,,k,);insert(*n*m,t,k,);
fillchar(num,sizeof(num),);
for i:= to n do for j:= to m do num[i,j]:=(i-)*m+j;
for i:= to n do
begin
for j:= to m do
begin
read(x);
insert(num[i,j],num[i,j]+n*m,,-x);
insert(num[i,j],num[i,j]+n*m,inf,);
insert(num[i,j]+n*m,num[i+,j],inf,);
insert(num[i,j]+n*m,num[i,j+],inf,);
end;
readln;
end;
end;
procedure main;
begin
mincost:=;
mcf;
writeln(-mincost);
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
init;
if k= then writeln() else main;
close(input);close(output);
end.
方法二：直接在spfa中把<改成>，其余一些预处理做修改
uses math;
const inf=maxlongint;
type node=record
from,go,next,v,c:longint;
end;
var e:array[..] of node;
pre,head,q,d:array[..] of longint;
v:array[..] of boolean;
num:array[..,..] of longint;
i,j,n,s,t,l,r,mincost,tot,k,x,m:longint;
procedure ins(x,y,z,w:longint);
begin
inc(tot);
with e[tot] do
begin
from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot;
end;
end;
procedure insert(x,y,z,w:longint);
begin
if y> then exit;
ins(x,y,z,w);ins(y,x,,-w);
end;
function spfa:boolean;
var i,x,y:longint;
begin
fillchar(v,sizeof(v),false);
for i:=s to t do d[i]:=-;
l:=;r:=;q[]:=s;d[s]:=;v[s]:=true;
while l<r do
begin
inc(l);
x:=q[l];v[x]:=false;
i:=head[x];
while i<> do
begin
y:=e[i].go;
if (e[i].v<>) and (d[x]+e[i].c>d[y]) then
begin
d[y]:=d[x]+e[i].c;
pre[y]:=i;
if not(v[y]) then
begin
v[y]:=true;
inc(r);
q[r]:=y;
end;
end;
i:=e[i].next;
end;
end;
exit(d[t]<>-);
end;
procedure mcf;
var i,tmp:longint;
begin
mincost:=;
while spfa do
begin
tmp:=inf;
i:=pre[t];
while i<> do
begin
tmp:=min(tmp,e[i].v);
i:=pre[e[i].from];
end;
inc(mincost,tmp*d[t]);
i:=pre[t];
while i<> do
begin
dec(e[i].v,tmp);
inc(e[i xor ].v,tmp);
i:=pre[e[i].from];
end;
end;
end;
procedure init;
begin
tot:=;
readln(k,m,n);
s:=;t:=*n*m+;
insert(s,,k,);insert(*n*m,t,k,);
fillchar(num,sizeof(num),);
for i:= to n do for j:= to m do num[i,j]:=(i-)*m+j;
for i:= to n do
begin
for j:= to m do
begin
read(x);
insert(num[i,j],num[i,j]+n*m,,x);
insert(num[i,j],num[i,j]+n*m,inf,);
insert(num[i,j]+n*m,num[i+,j],inf,);
insert(num[i,j]+n*m,num[i,j+],inf,);
end;
readln;
end;
end;
procedure main;
begin
mincost:=;
mcf;
writeln(mincost);
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
init;
if k= then writeln() else main;
close(input);close(output);
end.