传送门
这是个最大费用最大流，拆点连边就好啦，最大费用最大流
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
#define min(a,b) (a<b?a:b)
int n,k,cnt=1,sum,pre[60001],ans,nxt[60001],h[30001],b[30001],c[30001],s,t,v[60001],dis[30001],inf=1e9,w[30001];queue<int>q;bool vis[30001];
inline void add(int x,int y,int z,int u)
{
pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt,v[cnt]=z,w[cnt]=u;
pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt,v[cnt]=0,w[cnt]=-u;
}
inline bool spfa(int s)
{
memset(dis,63,sizeof dis);
q.push(s),dis[s]=0;
while(!q.empty())
{
int x=q.front();q.pop(),vis[x]=0;
for(rg int i=h[x];i;i=nxt[i])
if(v[i]&&dis[pre[i]]>dis[x]+w[i])
{
dis[pre[i]]=dis[x]+w[i],b[pre[i]]=x,c[pre[i]]=i;
if(!vis[pre[i]])vis[pre[i]]=1,q.push(pre[i]);
}
}
return dis[t]<inf;
}
inline int getans()
{
int mn=inf;
for(rg int i=t;i!=s;i=b[i])mn=min(v[c[i]],mn);
for(rg int i=t;i!=s;i=b[i])v[c[i]]-=mn,v[c[i]^1]+=mn;
return dis[t]*mn;
}
int main()
{
read(n),read(k),s=0,t=n*n*2+1,sum=n*n;
for(rg int i=1,x;i<=n;i++)
for(rg int j=1;j<=n;j++)
{
int a=(i-1)*n+j,b=a+1,c=a+n;
read(x),add(a,sum+a,inf,0),add(a,sum+a,1,-x);
if(j<n)add(sum+a,b,inf,0);
if(i<n)add(sum+a,c,inf,0);
}
add(s,1,k,0),add(t-1,t,k,0);
while(spfa(s))ans+=getans();
printf("%d
",-ans);
}