题目描述
在一个 N×N的矩形网格中,每个格子里都写着一个非负整数。可以从左上角到右下角安排K条路线,每一步只能往下或往右,沿途经过的格子中的整数会被取走。若多条路线重复经过一个格子,只取一次。
求能取得的整数的和最大是多少。
样例
输入格式
第一行包含两个整数 N和 K。接下来 N行,每行包含 N 个不超过 1000的整数,用来描述整个矩形网格。
输出格式
输出一个整数,表示能取得的最大和。
数据范围
1≤N≤50,0≤K≤10
输入样例:
3 2
1 2 3
0 2 1
1 4 2
输出样例:
15
算法1
有些赋值放在[ ]里面
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=5005, M=100010;
int ver[M],flux[M],cost[M],nxt[M],head[N],tot=1;
int d[N],minf[N],pre[N],n,k,S,T,ans;
bool inq[N];
void add(int x,int y, int c, int w){
ver[++tot]=y, flux[tot]=c, cost[tot]= w, nxt[tot]=head[x],head[x]=tot;
ver[++tot]=x, flux[tot]=0, cost[tot]=-w, nxt[tot]=head[y],head[y]=tot;
}
bool spfa(){
queue<int> q;
memset(d,-1,sizeof d);
d[S]=0, q.push(S),minf[S]=k,inq[S]=true;
while(q.size()){
auto x=q.front(); q.pop();
inq[x]=false; //不要忘了出队标记
for(int i=head[x],y; i ; i=nxt[i]){
if(!flux[i])continue;
if(d[ y=ver[i] ] >= d[x]+cost[i])continue; //必须>=,如果>,容易TLE
d[y]=d[x]+cost[ pre[y]=i ];
minf[y]=min(minf[x],flux[i]);
if(!inq[y]) q.push(y), inq[y]=true;
}
}
return d[T]!=-1;
}
void update(){
ans+=d[T]*minf[T];
for(int x=T,i; x!=S; x=ver[i^1])
flux[ i=pre[x] ] -=minf[T], flux[i^1] +=minf[T];
}
inline int num(int i,int j,bool inpoint){
return (i-1)*n+j+inpoint*n*n;
}
int main(){
cin>>n>>k;
for(int i=1,j=1,w;i<=n;j=1+(j%n),i+=(j==1)){
cin>>w;
add(num(i,j,0),num(i,j,1),1, w);//点分裂,0 -> 1;
add(num(i,j,0),num(i,j,1),k-1,0);
if(j<n)add(num(i,j,1),num(i,j+1,0),k,0);
if(i<n)add(num(i,j,1),num(i+1,j,0),k,0);
}
S=1, T=2*n*n; //从起点的起点,到终点的终点
while(spfa()) update();
cout<<ans<<endl;
}