$\color{deeppink}link$

本来只是看看费用流可以得多少分，没想到直接卡过了。

非常经典的骨牌问题。因为这些骨牌只会占用相邻的两个格子，那么可以想到用黑白染色来做。对于 $(x,y)$，若 $x+y\equiv 1\mod 2$，就连源点到该点一条容量为 $1$，费用为 $a_{x,y}$ 的边，再连该点到其四周的点，容量为 $1$ 费用为 $0$。否则就连该点到汇点的边，容量为 $1$ 费用为 $a_{x,y}$。

这是按照以上的思路打出来的代码：$link$。可以看到由于点有 $4e6$ 个，导致直接 MLE。但是，他没 T！这就给我一个优化空间的想法。

仔细看，对于所有的边，它的容量及费用极小，甚至可以不用整型来存，用短整型来存即可。可以优化差不多一半的空间，可以过了。

$code$

#include<bits/stdc++.h>
#define ll long long
#define sh short
using namespace std;
const int N=4e6+500,M=4e7+500,inf=1e9+7;

struct node
{
	int u,v,nxt;
	sh c,w;
}e[M];

int n,m,head[N],k,a[2300][2300],cnt=1,st,ed;
int rx[4]={0,0,1,-1},ry[4]={1,-1,0,0};
ll tot;

void add(int u,int v,int w,int c)
{
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].c=c;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

int id(int x,int y)
{
	return (x-1)*n+y;
}

void read()
{
	cin>>n>>k;int s=n*n+1;st=s+1,ed=st+1;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],tot+=a[i][j];
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		if((i+j)&1)continue;
		for(int k=0;k<4;k++)
		{
			int xx=i+rx[k],yy=j+ry[k];
			if(xx<1||xx>n||yy<1||yy>n)continue;
			add(id(i,j),id(xx,yy),1,0);
			add(id(xx,yy),id(i,j),0,0);
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		if((i+j)&1)add(id(i,j),ed,1,-a[i][j]),add(ed,id(i,j),0,a[i][j]);
		else add(s,id(i,j),1,-a[i][j]),add(id(i,j),s,0,a[i][j]);
	}
	add(st,s,k,0);add(s,st,0,0);
}

int vis[N],dep[N],maxflow;
ll mincost;

int spfa()
{
	deque<int>q;
	for(int i=1;i<=ed;i++)vis[i]=0,dep[i]=inf;
	q.push_back(ed);vis[ed]=1;dep[ed]=0;
	while(!q.empty())
	{
		int x=q.front();q.pop_front();vis[x]=0;
		for(int i=head[x];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(e[i^1].w>0&&dep[v]>dep[x]-e[i].c)
			{
				dep[v]=dep[x]-e[i].c;
				if(!vis[v])
				{
					vis[v]=1;
					if(!q.empty()&&dep[v]<dep[q.front()])q.push_front(v);
					else q.push_back(v);
				}
			}
		}
	}
	return dep[st]<inf;
}

int dfs(int now,int flow)
{
	vis[now]=1;
	if(now==ed||flow<=0)return flow;
	int res=0;
	for(int i=head[now];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(!vis[v]&&e[i].w&&dep[now]-e[i].c==dep[v])
		{
			int d=dfs(v,min(flow-res,int(e[i].w)));
			if(d<=0)continue;
			e[i].w-=d,e[i^1].w+=d;
			res+=d,mincost+=1ll*d*e[i].c;
			if(res==flow)return res;
		}
	}
	return res;
}

void zkw()
{
	while(spfa())
	{
		vis[ed]=1;
		while(vis[ed])
		{
			for(int i=1;i<=ed;i++)vis[i]=0;
			maxflow+=dfs(st,inf);
		}
	}
}

void print()
{
	cout<<tot+mincost;
}

main()
{
	read();
	zkw();
	print();
}