拆点后入点和出点两条（容量，边权）为的边
求解最大流需要寻找所以一条增广路，为了费用之和最小，可以改用spfa寻找一条单位费用之和最小的增广路，每次在残余网络中跑最长路，直到找到最大流。
这题不要求最大流，所以如果残余网络中得不到费用后可以直接退出。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=5010,maxm=200010;
typedef long long int ll;

int head[maxn],Next[maxm],to[maxm],edge[maxm],tot=1,d[maxn],s,t,now[maxn],n,k;
int pre[maxn],incf[maxn],cost[maxm];
void add(int x,int y,int z,int c) {
    to[++tot]=y; Next[tot]=head[x]; head[x]=tot; edge[tot]=z; cost[tot]=c;
    to[++tot]=x; Next[tot]=head[y]; head[y]=tot; edge[tot]=0; cost[tot]=-c;
}
inline int num(int x,int y,int k) {
    return (x-1)*n+y+k*n*n;
}
queue<int>que;
bool vis[maxn];
bool spfa() {
    while(que.size()) que.pop();
    memset(d,0xcf,sizeof(d));//-inf
    memset(vis,0,sizeof vis);
    que.push(s); d[s]=0; vis[s]=1;
    int x,y; incf[s]=0x3f3f3f3f;
    while(que.size()) {
        x=que.front(); que.pop(); vis[x]=0;
        for(int i=head[x],y=to[i];i;i=Next[i],y=to[i]) {
            if(!edge[i]) continue;
            if(d[y]<d[x]+cost[i]) {
                d[y]=d[x]+cost[i];
                incf[y]=min(incf[x],edge[i]);//最小流量 
                pre[y]=i;//记录前驱 
                if(!vis[y]) {
                    que.emplace(y); vis[y]=1;
                }
            }
        }
    }
    if(d[t]==0xcfcfcfcf) return false;
    return true;
}
void update(int &ans) {
    int x=t,i;
    while(x!=s) {
        i=pre[x];
        edge[i]-=incf[t];
        edge[i^1]+=incf[t];
        x=to[i^1];
    }
//    maxflow+=incf[t];
    ans+=d[t]*incf[t];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    s=1,t=2*n*n;
    for(int i=1,c;i<=n;++i)
    for(int j=1;j<=n;++j) {
        cin>>c;
        add(num(i,j,0),num(i,j,1),1,c);    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);
    }
    int ans(0);
    while(spfa()) update(ans);
    cout<<ans<<'\n';
}