[洛谷P2045]方格取数加强版

题目大意：有一个n*n的矩阵，每个格子有一个非负整数，规定一个人从(1,1)开始，只能往右或下走，走到(n,n)为止，并把沿途的数取走，取走后数变为0。这个人共取n次，求取得的数的最大总和。

解题思路：由于取多少次不确定，所以不能用dp。

我们发现，一个格子只能从左边或上面走来，且数只能取到一次，那么我们可以把此题转化为最大费用最大流问题。首先拆点，将一个点拆成x和y，然后从x到y连一条容量为1，流量为x(x为这格的数)的边，然后再连一条容量为inf，费用为0的边，这样即可保证一个点可以走多次，而数只能取一次。然后连接a和b时，从a的y向b的x连一条容量为inf，费用为0的边。最后跑最大费用最大流即可。

实现时对于(i,j)，我们把这个点的x编号为$(i-1)*n+j$，y编号为$(i-1)*n+j+n^2$即可。

以下为EK算法代码。

C++ Code：

#include<cstdio>

#include<vector>

#include<queue>

#include<string.h>

using namespace std;

#define inf 0x3f3f3f3f

#define N 1000000

struct edge{

	int from,to,cap,cost,nxt;

}e[N];

int n,k,dis[N],a[N],pree[N],head[N],cnt;

bool vis[N];

queue<int>q;

inline void addedge(int from,int to,int cap,int cost){

	e[++cnt]=(edge){from,to,cap,cost,head[from]};

	head[from]=cnt;

	e[++cnt]=(edge){to,from,0,-cost,head[to]};

	head[to]=cnt;

}

bool spfa(int s,int t,int& flow,int& cost){

	memset(pree,0,sizeof(pree));

	memset(a,0x3f,sizeof(a));

	memset(dis,200,sizeof(dis));

	memset(vis,0,sizeof(vis));

	vis[s]=1;

	dis[s]=0;

	q.push(s);

	while(!q.empty()){

		int u=q.front();

		q.pop();

		vis[u]=0;

		for(int i=head[u];i;i=e[i].nxt){

			if(e[i].cap>0&&dis[e[i].to]<dis[u]+e[i].cost){

				dis[e[i].to]=dis[u]+e[i].cost;

				pree[e[i].to]=i;

				if(a[u]>e[i].cap)a[e[i].to]=e[i].cap;else a[e[i].to]=a[u];

				if(!vis[e[i].to]){

					vis[e[i].to]=1;

					q.push(e[i].to);

				}

			}

		}

	}

	if(dis[t]<1)return false;

	flow+=a[t];

	cost+=a[t]*dis[t];

	for(int i=t;i!=s;i=e[pree[i]].from){

		e[pree[i]].cap-=a[t];

		e[pree[i]^1].cap+=a[t];

	}

	return true;

}

int main(){

	cnt=1;

	scanf("%d%d",&n,&k);

	int m=n*n;

	for(int i=1;i<=n;++i){

		for(int j=1;j<=n;++j){

			int x;

			scanf("%d",&x);

			addedge((i-1)*n+j,(i-1)*n+j+m,inf,0);

			addedge((i-1)*n+j,(i-1)*n+j+m,1,x);

			if(i>1){

				addedge((i-2)*n+j+m,(i-1)*n+j,inf,0);

			}

			if(j>1){

				addedge((i-1)*n+j-1+m,(i-1)*n+j,inf,0);

			}

			if(i==1&&j==1){

				addedge(0,1,inf,0);

			}

		}

	}

	int flow=0,cost=0;

	while(k--)

	if(!spfa(0,m<<1,flow,cost))break;

	printf("%d\n",cost);

	return 0;

}