K方格取数

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入格式
第一行两个数n,k（1<=n<=50, 0<=k<=10）

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式
一个数,为最大和

输入输出样例

输入
3 1
1 2 3
0 2 1
1 4 2
输出
11

相信做到这道题，大多数人应该做过k等于2的情况吧，当k等于2时，我们可以直接dp，令 dp[i][j][k][l] 为第一个人走到（i，j），第二个人走到（k，l）的情况，就可以很容易dp出来。

但是有了网络流，还要dp干嘛？

对于这道题，考虑建图：

不难看出，这道题我们有两个要关注的东西，就是取k次，和最大和。

那么我们把每个点拆成两个点，这两个点分为入点和出点。

入点到出点有两条边，第一条的费用为当前格子的值，流量为1，第二条的费用为0，流量为k-1；然后出点指向相邻的两个格子的入点。

这样我们求点（1,1）到（n，n）的最大费用流就可以了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=5510;
int n,k,g[55][55],s,t,d[N];
int head[N],nex[N<<2],fl[N<<2],w[N<<2],to[N<<2],tot=1;
struct node{
	int v,e;
}p[N];
inline void add(int a,int b,int c,int d){
	fl[++tot]=c; to[tot]=b; w[tot]=d; nex[tot]=head[a]; head[a]=tot;
	fl[++tot]=0; to[tot]=a; w[tot]=-d; nex[tot]=head[b]; head[b]=tot;
}
inline int num(int i,int j,int k){
	return (i-1)*n+j+k*n*n;//把坐标离散化 
}
bool spfa(){
	int vis[N]={0};	queue<int> q;	q.push(s);	vis[s]=1;
	memset(d,0xcf,sizeof d);	d[s]=0;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(fl[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				p[to[i]].v=u;	p[to[i]].e=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=0xcfcfcfcf;//-INF
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=p[i].v)	mi=min(mi,fl[p[i].e]);
		for(int i=t;i!=s;i=p[i].v){
			fl[p[i].e]-=mi;	fl[p[i].e^1]+=mi;
		}
		res+=d[t]*mi;
	}
	return res;
}
int main(){
	cin>>n>>k;	s=num(1,1,0);	t=num(n,n,1);//s到t的费用流 
	for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	cin>>g[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			add(num(i,j,0),num(i,j,1),1,g[i][j]);
			add(num(i,j,0),num(i,j,1),k-1,0);
			if(i<n)	add(num(i,j,1),num(i+1,j,0),k,0);
			if(j<n)	add(num(i,j,1),num(i,j+1,0),k,0);
		}
	}
	cout<<EK()<<endl;
	return 0;
}