【洛谷2045】方格取数

题目大意：给定一个 N*N 的矩阵，点有点权，现进行 k 次从左上角到右下角的寻路操作，对于每个点可以向右或向下走。每走到一个点，若之前没走过这个点，答案加上该点点权。求进行 k 次操作后，可以获得的最大点权和是多少。

题解：对于每个点都有一个权值，且权值只能被使用一次，同一个点最多可以经过 k 次。考虑进行拆点，即：将矩形中每一个点都拆成两个点，比如 u，拆成 u,u'，u 为入点，u' 为出点，在入点和出点之间连一条容量是 1，费用是点权的边，再连一条容量是 k-1，费用是 0 的边。同理，连接当前点的出点和右方、下方的入点，容量为 k，费用为 0。再在图上跑最大费用最大流即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
const int maxm=5e4+10;
const int inf=0xcfcfcfcf;

int ans;
int n,k,s,t,d[maxn],pre[maxn],now[maxn];
bool in[maxn];
struct node{int nxt,to,w,c;}e[maxm<<1];
int tot=1,head[maxn];
inline void add_edge(int from,int to,int w,int c){
	e[++tot]=node{head[from],to,w,c},head[from]=tot;
	e[++tot]=node{head[to],from,0,-c},head[to]=tot;
}
inline int get(int i,int j,int k){return n*(i-1)+j+k*n*n;}
bool spfa(){
	queue<int> q;
	memset(in,0,sizeof(in));
	memset(d,0xcf,sizeof(d));
	in[s]=1,now[s]=0x3f3f3f3f,d[s]=0,q.push(s);
	while(q.size()){
		int u=q.front();q.pop(),in[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].w,c=e[i].c;
			if(w&&d[v]<d[u]+c){
				d[v]=d[u]+c;
				now[v]=min(now[u],w);
				pre[v]=i;
				if(!in[v])in[v]=1,q.push(v);
			}
		}
	}
	return d[t]!=inf;
}
void update(){
	ans+=d[t]*now[t];
	int x=t;
	while(x!=s){
		int i=pre[x];
		e[i].w-=now[t];
		e[i^1].w+=now[t];
		x=e[i^1].to;
	}
}

void read_and_parse(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			int c;scanf("%d",&c);
			add_edge(get(i,j,0),get(i,j,1),1,c);
			add_edge(get(i,j,0),get(i,j,1),k-1,0);
			if(i<n)add_edge(get(i,j,1),get(i+1,j,0),k,0);
			if(j<n)add_edge(get(i,j,1),get(i,j+1,0),k,0);
		}
}
void solve(){
	s=1,t=n*n*2;
	while(spfa())update();
	printf("%d
",ans);
}
int main(){
	read_and_parse();
	solve();
	return 0;
}