题目 | 记录

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+5,M=1e6+5;
int n,k,s,t;
int tot1=1,head1[N],to[M],nxt[M];
ll w1[M],c1[M],d1[N],cst,a[105][105],inf=0x3f3f3f3f3f3f3f3f;
bool vis1[N];
char *p1,*p2,buf[10000005];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;char ch=nc();
    while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
    while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();
   	return x*f;
}
void pre(){
	memset(head1,0,sizeof head1);
	tot1=1;
	cst=0;
}
void add1(int u,int v,ll w,ll cost){
	to[++tot1]=v;
	nxt[tot1]=head1[u];
	w1[tot1]=w;
	c1[tot1]=cost;
	head1[u]=tot1;
}
void add2(int u,int v,ll w,ll cost){
	add1(u,v,w,cost);
	add1(v,u,0,-cost);
}
bool bfs(){
	queue<int>q;
	memset(d1,0x3f,sizeof(d1));
	d1[s]=0;
	vis1[s]=1;
	q.emplace(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis1[u]=0;
		for(int i=head1[u];i>1;i=nxt[i]){
			ll v=to[i];
			if(w1[i]&&d1[v]>d1[u]+c1[i]){
				d1[v]=d1[u]+c1[i];
				if(!vis1[v])
					vis1[v]=1,q.emplace(v);
			}
		}
	}
	return d1[t]^inf;
}
ll dfs(ll x,ll p){
	if(x==t)
		return p;
	vis1[x]=1;
	ll pos=p;
	for(int i=head1[x],y;i>1&&pos;i=nxt[i]){
		y=to[i];
		if((!vis1[y])&&w1[i]&&(d1[y]==d1[x]+c1[i])){
			ll h=dfs(y,min(pos,w1[i]));
			if(!h)
				d1[y]=inf;
			else
				w1[i]-=h,
				w1[i^1]+=h,
				cst+=h*c1[i],
				pos-=h;
		}
	}
	vis1[x]=0;
	return p-pos;
}
ll Dinic(){
	ll res=0;
	while(bfs())
		res+=dfs(s,inf);
	return res;
}
int yyz(int x,int y){
	return (x-1)*n+y;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%lld",&a[i][j]);
	s=1,t=n*n*2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i>1||j>1)
				add2(yyz(i,j),yyz(i,j)+n*n,k,-a[i][j]);
			else
				add2(yyz(i,j),yyz(i,j)+n*n,k,-a[i][j]);
	for(int i=1;i<n;i++)
		for(int j=1;j<=n;j++)
			add2(yyz(i,j)+n*n,yyz(i+1,j),k,0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<n;j++)
			add2(yyz(i,j)+n*n,yyz(i,j+1),k,0);
	Dinic();
	return printf("%lld\n",-cst),0;
}