费用流，其实是求传输一个容量为k的流的最大费用。主要是建图。原点为0，和1连上一条容量为k，费用为0的边，中间每个点拆成两个1和2，连上一条边，容量为k，费用为c，再连一条容量为比k大，费用为0的边，这样是为了跑完费用之后能继续跑拆完后的点和。然后和其他边连上就可以了。n*n和汇点连上一条容量为k，费用为0的边。我就是每次跑了一个容量为1的流，求打脸，不知道对不对。
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
struct edge
{
int to,nxt,c,f;
}e[];
int n,k,cur,ans,cnt=;
int dist[],used[],pree[],prev[],g[];
void link(int u,int v,int f,int c)
{
e[++cnt].nxt=g[u];
g[u]=cnt;
e[cnt].f=f;
e[cnt].to=v;
e[cnt].c=c;
}
void ins(int u,int v,int f,int c)
{
link(u,v,f,c);
link(v,u,,-c);
}
int Min(int x,int y)
{
return x<y?x:y;
}
bool spfa()
{
queue<int>q;
memset(dist,-,sizeof(dist));
memset(used,,sizeof(used));
dist[]=;
q.push();
while(!q.empty())
{
int u=q.front(); q.pop();
used[u]=;
for(int i=g[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].c;
if(e[i].f&&dist[v]<dist[u]+w)
{
dist[v]=dist[u]+w;
prev[v]=u; pree[v]=i;
if(!used[v])
{
q.push(v);
used[v]=;
}
}
}
}
return dist[]!=-;
}
int MinCostFlow()
{
int u=,sum=inf;
while(u)
{
e[pree[u]].f--;
e[pree[u]^].f++;
u=prev[u];
}
// cout<<dist[10010]<<endl;
return dist[];
}
void MinFlow()
{
while(spfa())
{
cur+=MinCostFlow();
if(cur>ans) ans=cur;
}
printf("%d",ans);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
int x; scanf("%d",&x);
ins((i-)*n+j,(i-)*n+j+n*n,,x);
ins((i-)*n+j,(i-)*n+j+n*n,k,);
if(i!=n)
{
ins((i-)*n+j+n*n,i*n+j,k,);
}
if(j!=n)
{
ins((i-)*n+j+n*n,(i-)*n+j+,k,);
}
}
}
ins(,,k,);
ins(n*n*,,k,);
MinFlow();
return ;
}