首页 > 代码库 > vijos 1563 疯狂的方格取数
vijos 1563 疯狂的方格取数
P1653疯狂的方格取数
Accepted
标签：天才的talent[显示标签]
背景
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
样例输入1[复制]
4 6 70 2 3 4 5 66 5 4 3 2 10 9 8 7 6 512 3 4 5 6 70 0 0 1 2 312 23 34 45 1 234 5 6 6 1 0
样例输出1[复制]
265
限制
共有10个测试数据，每个测试数据包含1个测试点，每个测试点的时间限制为2秒钟。
来源
本题目来自：北京市，中关村中学，高三9班，孙一（网名:talent123
题解：
当年的难题如今终于轻松解决了……
不多说了，水题一道……
网络流想几道基本上就差不多了……
最大费用最大流
代码：
方法一：将费用取负
1 uses math; 2 const inf=maxlongint; 3 type node=record 4 from,go,next,v,c:longint; 5 end; 6 var e:array[0..200000] of node; 7 pre,head,q,d:array[0..100000] of longint; 8 v:array[0..100000] of boolean; 9 num:array[0..100,0..100] of longint; 10 i,j,n,s,t,l,r,mincost,tot,k,x,m:longint; 11 procedure ins(x,y,z,w:longint); 12 begin 13 inc(tot); 14 with e[tot] do 15 begin 16 from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot; 17 end; 18 end; 19 procedure insert(x,y,z,w:longint); 20 begin 21 if y>100000 then exit; 22 ins(x,y,z,w);ins(y,x,0,-w); 23 end; 24 function spfa:boolean; 25 var i,x,y:longint; 26 begin 27 fillchar(v,sizeof(v),false); 28 for i:=s to t do d[i]:=inf; 29 l:=0;r:=1;q[1]:=s;d[s]:=0;v[s]:=true; 30 while l<r do 31 begin 32 inc(l); 33 x:=q[l];v[x]:=false; 34 i:=head[x]; 35 while i<>0 do 36 begin 37 y:=e[i].go; 38 if (e[i].v<>0) and (d[x]+e[i].c<d[y]) then 39 begin 40 d[y]:=d[x]+e[i].c; 41 pre[y]:=i; 42 if not(v[y]) then 43 begin 44 v[y]:=true; 45 inc(r); 46 q[r]:=y; 47 end; 48 end; 49 i:=e[i].next; 50 end; 51 end; 52 exit(d[t]<>inf); 53 end; 54 procedure mcf; 55 var i,tmp:longint; 56 begin 57 mincost:=0; 58 while spfa do 59 begin 60 tmp:=inf; 61 i:=pre[t]; 62 while i<>0 do 63 begin 64 tmp:=min(tmp,e[i].v); 65 i:=pre[e[i].from]; 66 end; 67 inc(mincost,tmp*d[t]); 68 i:=pre[t]; 69 while i<>0 do 70 begin 71 dec(e[i].v,tmp); 72 inc(e[i xor 1].v,tmp); 73 i:=pre[e[i].from]; 74 end; 75 end; 76 end; 77 procedure init; 78 begin 79 tot:=1; 80 readln(k,m,n); 81 s:=0;t:=2*n*m+1; 82 insert(s,1,k,0);insert(2*n*m,t,k,0); 83 fillchar(num,sizeof(num),60); 84 for i:=1 to n do for j:=1 to m do num[i,j]:=(i-1)*m+j; 85 for i:=1 to n do 86 begin 87 for j:=1 to m do 88 begin 89 read(x); 90 insert(num[i,j],num[i,j]+n*m,1,-x); 91 insert(num[i,j],num[i,j]+n*m,inf,0); 92 insert(num[i,j]+n*m,num[i+1,j],inf,0); 93 insert(num[i,j]+n*m,num[i,j+1],inf,0); 94 end; 95 readln; 96 end; 97 end; 98 procedure main; 99 begin100 mincost:=0;101 mcf;102 writeln(-mincost);103 end;104 begin105 assign(input,‘input.txt‘);assign(output,‘output.txt‘);106 reset(input);rewrite(output);107 init;108 if k=0 then writeln(0) else main;109 close(input);close(output);110 end.
方法二：直接在spfa中把<改成>，其余一些预处理做修改
1 uses math; 2 const inf=maxlongint; 3 type node=record 4 from,go,next,v,c:longint; 5 end; 6 var e:array[0..200000] of node; 7 pre,head,q,d:array[0..100000] of longint; 8 v:array[0..100000] of boolean; 9 num:array[0..100,0..100] of longint; 10 i,j,n,s,t,l,r,mincost,tot,k,x,m:longint; 11 procedure ins(x,y,z,w:longint); 12 begin 13 inc(tot); 14 with e[tot] do 15 begin 16 from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot; 17 end; 18 end; 19 procedure insert(x,y,z,w:longint); 20 begin 21 if y>100000 then exit; 22 ins(x,y,z,w);ins(y,x,0,-w); 23 end; 24 function spfa:boolean; 25 var i,x,y:longint; 26 begin 27 fillchar(v,sizeof(v),false); 28 for i:=s to t do d[i]:=-1; 29 l:=0;r:=1;q[1]:=s;d[s]:=0;v[s]:=true; 30 while l<r do 31 begin 32 inc(l); 33 x:=q[l];v[x]:=false; 34 i:=head[x]; 35 while i<>0 do 36 begin 37 y:=e[i].go; 38 if (e[i].v<>0) and (d[x]+e[i].c>d[y]) then 39 begin 40 d[y]:=d[x]+e[i].c; 41 pre[y]:=i; 42 if not(v[y]) then 43 begin 44 v[y]:=true; 45 inc(r); 46 q[r]:=y; 47 end; 48 end; 49 i:=e[i].next; 50 end; 51 end; 52 exit(d[t]<>-1); 53 end; 54 procedure mcf; 55 var i,tmp:longint; 56 begin 57 mincost:=0; 58 while spfa do 59 begin 60 tmp:=inf; 61 i:=pre[t]; 62 while i<>0 do 63 begin 64 tmp:=min(tmp,e[i].v); 65 i:=pre[e[i].from]; 66 end; 67 inc(mincost,tmp*d[t]); 68 i:=pre[t]; 69 while i<>0 do 70 begin 71 dec(e[i].v,tmp); 72 inc(e[i xor 1].v,tmp); 73 i:=pre[e[i].from]; 74 end; 75 end; 76 end; 77 procedure init; 78 begin 79 tot:=1; 80 readln(k,m,n); 81 s:=0;t:=2*n*m+1; 82 insert(s,1,k,0);insert(2*n*m,t,k,0); 83 fillchar(num,sizeof(num),60); 84 for i:=1 to n do for j:=1 to m do num[i,j]:=(i-1)*m+j; 85 for i:=1 to n do 86 begin 87 for j:=1 to m do 88 begin 89 read(x); 90 insert(num[i,j],num[i,j]+n*m,1,x); 91 insert(num[i,j],num[i,j]+n*m,inf,0); 92 insert(num[i,j]+n*m,num[i+1,j],inf,0); 93 insert(num[i,j]+n*m,num[i,j+1],inf,0); 94 end; 95 readln; 96 end; 97 end; 98 procedure main; 99 begin100 mincost:=0;101 mcf;102 writeln(mincost);103 end;104 begin105 assign(input,‘input.txt‘);assign(output,‘output.txt‘);106 reset(input);rewrite(output);107 init;108 if k=0 then writeln(0) else main;109 close(input);close(output);110 end.111
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。