K取方格数（最大费用流）

题目描述
给定\(n\times m\)的方格\(a[1..n][1..m]\)，每个格子有一个数。

从\((1,1)\)出发走到\((n,m)\)一共不超过\(K\)次，只能往右往下走，走过的位置的数会变成\(0\)。

问经过的位置的数字之和的最大值是多少。
输入
第一行包含一个正整数\(T(1\leq T\leq 10)\)，表示测试数据的组数。

每组数据第一行包含三个正整数\(n,m,K(1\leq n,m,K\leq 10)\)。

接下来\(n\)行，每行\(m\)个正整数，第\(i\)行第\(j\)个数表示\(a[i][j](1\leq a[i][j]\leq 10000)\)。
输出
对于每组数据输出一行一个整数，即和的最大值。

拆点实现取一次获得a[i][j]且取完为0

#include<bits/stdc++.h>
using namespace std;
const int N = 1000,M = 100000,INF = 0x3f3f3f3f;
int h[N],e[M],ne[M],f[M],w[M],idx;
int d[N],flow[N],pre[N];
bool st[N];
queue<int> q;
//a->b一条流量为c,费用为d的边
void add(int a,int b,int c,int d){
   e[idx] =b,f[idx] =c,w[idx]= d,ne[idx]= h[a],h[a]= idx++;
   e[idx] =a,f[idx] =0,w[idx]=-d,ne[idx]= h[b],h[b] = idx++;
}
bool spfa(int s,int t){
    memset(d,0x3f,sizeof d);
	memset(flow,0,sizeof flow);
	d[s] = 0,flow[s] =0x3f3f3f3f;
	q.push(s);

	while(q.size())
	{
	int u = q.front();
	q.pop();
	st[u]= 0;
 
	for(int i = h[u];i!=-1;i = ne[i])
	{
		int v =e[i];
	
		if(f[i] && d[v] > d[u]+ w[i])
		{
			d[v] =d[u] + w[i];
			pre[v] =i;
			flow[v]= min(f[i],flow[u]);

			if(!st[v])
			{
				q.push(v);
				st[v]= 1;
			}
		}
	}
	}
	return flow[t] > 0;
}
pair<int,int> EK(int s,int t){
	int maxflow= 0,mincost =0;
	while(spfa(s,t)){
	int r = flow[t];
	maxflow+= r,mincost += r* d[t];

	for(int i = t;i !=s;i = e[pre[i]^ 1]){
	f[pre[i]]-=r;
	f[pre[i]^ 1] += r;
	}
 	}	
    return make_pair(maxflow,mincost);
	}
int n,m,k;
int a[N][N],mp[N][N],fmp[N][N];
//mp[i][j]是a[i][j]的映射,fmp[i][j]是a[i][j]的拆点
void solve()
{
	cin>>n>>m>>k;
	int s = 0, t = n*m*2+1;
	memset(h,-1,sizeof h);

	for(int i=1;i<=n;++i)
	 for(int j=1;j<=m;++j)
	 cin>>a[i][j];
	for(int i=1;i<=n;++i)
	 for(int j=1;j<=m;++j)
	 mp[i][j] = (i-1)*m+j, fmp[i][j] = n*m+mp[i][j];
	//从源点向(1,1)连一条容量为k,费用为0的边,表示至多从源点走k次
	add(s,mp[1][1],k,0);
	add(fmp[n][m],t,k,0);
	for(int i=1;i<=n;++i)
	 for(int j=1;j<=m;++j)
	 {
	 	//从源点向拆点连接两条边,一条[INF,0]表示可以经过无数次，费用为0
	 	//一条表示只能经过一次费用为a[i][j]
	 	add(mp[i][j],fmp[i][j],INF,0),add(mp[i][j],fmp[i][j],1,-a[i][j]);
	    //向下和右建边
	    if(j!=m) add(fmp[i][j],mp[i][j+1],INF,0);
	    if(i!=n) add(fmp[i][j],mp[i+1][j],INF,0);
	 }
	 
	//求出mincost取反
	auto [maxflow,mincost] = EK(s,t);
	cout<< -mincost <<'\n';
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}