比较简单的费用流.
我们发现题目中有几个性质：
1. 总共走 k 次.
2. 每个格子可以无限经过.
3. 每个格子最多只能贡献 1 次.
根据上述条件，我们就将每个格子进行拆点，拆成入点和出点.
入点向出点连一条 $(1,a[i][j])$ 的边，表示贡献.
入点向出点连一条 $(+infty,0)$ 的边，表示只是经过，但不贡献.
然后对于相邻点的话就从一个点的出点连到另一个点的入点就行了.
再设超级源点，超级汇点就行了.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=10000+3;
const int INF=100000+123;
int s,t,n;
struct Edge{
int from,to,cap,cost;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),cost(f){}
};
struct MCMF{
vector<Edge>edges;
vector<int>G[maxn];
int d[maxn],inq[maxn],a[maxn],flow2[maxn];
queue<int>Q;
ll ans=0;
int flow=0;
void addedge(int u,int v,int c,int f){
edges.push_back(Edge(u,v,c,f)); //正向弧
edges.push_back(Edge(v,u,0,-f)); //反向弧
int m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int SPFA(){
for(int i=0;i<=n*2;++i)d[i]=INF,flow2[i]=INF;
memset(inq,0,sizeof(inq));
int f=INF;
d[s]=0,inq[s]=1;Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();inq[u]=0;
int sz=G[u].size();
for(int i=0;i<sz;++i){
Edge e=edges[G[u][i]];
if(e.cap>0&&d[e.to]>d[u]+e.cost){
a[e.to]=G[u][i];
d[e.to]=d[u]+e.cost;
flow2[e.to]=min(flow2[u],e.cap);
if(!inq[e.to]){inq[e.to]=1;Q.push(e.to);}
}
}
}
if(d[t]==INF||d[t]==0)return 0;
f=flow2[t];
flow+=f;
int u=edges[a[t]].from;
edges[a[t]].cap-=f;
edges[a[t]^1].cap+=f;
while(u!=s){
edges[a[u]].cap-=f;
edges[a[u]^1].cap+=f;
u=edges[a[u]].from;
}
ans+=(ll)(d[t])*(-1);
return 1;
}
ll maxflow(){
while(SPFA());
return ans;
}
};
int main(){
int siz,k,cnt=0;
MCMF op;
scanf("%d%d",&siz,&k);
n=siz*siz;
for(int i=1;i<=siz;++i)
for(int j=1;j<=siz;++j){
int c;scanf("%d",&c);
++cnt;
op.addedge(cnt,cnt+1,1,-c);
op.addedge(cnt,cnt+1,INF,0);
++cnt;
}
t=cnt;
cnt=0;
for(int i=1;i<=siz;++i)
for(int j=1;j<=siz;++j){
cnt+=2;
if(i+1<=siz)op.addedge(cnt,cnt+(siz*2-1),INF,0);
if(j+1<=siz)op.addedge(cnt,cnt+1,INF,0);
}
s=0;
op.addedge(s,1,k,0);
printf("%lld",op.maxflow());
return 0;
}