【题意】
给定一个n*n的方格,每个方格里有一个数,从左上角出发,只能向下走或向右走,取过的数不计算权值,问走k次能得到的最大权值和
【输入】
第一行两个数字n、k
接下来一个n*n的矩阵描述棋盘
【输出】
一个数字表示最大的权值和
最大费用最大流,每个网格拆成两个点,之间连一条格子权值的流量为1的边和权值为0的流量为k-1的边,每个格子拆成的后一个点向能通往的格子的前一个点连一条权值为0流量为k的边,然后源点向(1,1)的前一个点连权值为0流量为k的边,(n,n)向汇点连权值为0流量为k的边,图就建好了,之后求费用流即可,虽然点最多有5002个,但是边十分稀疏,所以还是很轻松就能过的
program poj3422; const s=0; e=5101; var max,ans,p,n,k,i,j,tot:longint; dis,last,root:array [0..5101] of longint; dl,next,cost,point,flow:array [0..600001] of longint; function hash (x,y,s:longint):longint;inline; begin exit(x*n-n+y+s*n*n); end; function anti (now:longint):longint;inline; begin if now and 1 = 1 then exit(now+1) else exit(now-1); end; procedure connect (u,v,f,c:longint);inline; begin inc(tot); point[tot]:=v; flow[tot]:=f; cost[tot]:=c; next[tot]:=root[u]; root[u]:=tot; end; function mcmf:longint; begin ans:=0; repeat fillchar(dis,sizeof(dis),0); dis[s]:=1; dl[0]:=s; tot:=0; i:=0; while i<=tot do begin k:=root[dl[i]]; while k<>0 do begin if (flow[k]>0)and(dis[point[k]]<dis[dl[i]]+cost[k]) then begin dis[point[k]]:=dis[dl[i]]+cost[k]; inc(tot); dl[tot]:=point[k]; last[point[k]]:=k; end; k:=next[k]; end; inc(i); end; if dis[e]<=1 then break; max:=maxlongint;; i:=e; while i<>s do begin if flow[last[i]]<max then max:=flow[last[i]]; i:=point[anti(last[i])]; end; ans:=ans+max*(dis[e]-1); i:=e; while i<>s do begin flow[last[i]]:=flow[last[i]]-max; flow[anti(last[i])]:=flow[anti(last[i])]+max; i:=point[anti(last[i])]; end; until false; exit(ans); end; begin read(n,k); for i:=1 to n do for j:=1 to n do begin read(p); connect(hash(i,j,0),hash(i,j,1),1,p); connect(hash(i,j,1),hash(i,j,0),0,-p); connect(hash(i,j,0),hash(i,j,1),k-1,0); connect(hash(i,j,1),hash(i,j,0),0,0); if i+1<=n then begin connect(hash(i,j,1),hash(i+1,j,0),k,0); connect(hash(i+1,j,0),hash(i,j,1),0,0); end; if j+1<=n then begin connect(hash(i,j,1),hash(i,j+1,0),k,0); connect(hash(i,j+1,0),hash(i,j,1),0,0); end; end; connect(s,hash(1,1,0),k,0); connect(hash(1,1,0),s,0,0); connect(hash(n,n,1),e,k,0); connect(e,hash(n,n,1),0,0); writeln(mcmf); end.