最小费用最大流。
建图方式如图所示
然后就是费用流的模板~~
把最小费用转化成最大费用，做法一样。
还有一种做法，就是把所有的边的费用取负，然后去最小费用，然后去负值就好。‘
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define INF 99999999
#define maxn 5050
#define LL long long
struct list
{int l;int r;int v;int f;int next;
}node[1000001];
int num;
int head[1000001];
int pre[maxn];
int n,k;
int st,ed;
LL ans;
int ns;
void add(int l,int r,int v,int f)
{node[num].l=l;node[num].r=r;node[num].v=v;node[num].f=f;node[num].next=head[l];head[l]=num++;node[num].l=r;node[num].r=l;node[num].v=-v;node[num].f=0;node[num].next=head[r];head[r]=num++;
}
int bfs()
{int visit[maxn];int dist[maxn];int i;for(i=0;i<=ns;i++)dist[i]=-1;memset(visit,0,sizeof(visit));memset(pre,-1,sizeof(pre));queue<int >q;q.push(0);dist[0]=0;visit[0]=1;while(!q.empty()){int e=q.front();q.pop();visit[e]=0;for(i=head[e];i!=-1;i=node[i].next){int r=node[i].r;if(dist[r]<dist[e]+node[i].v&&node[i].f>0){pre[r]=i;dist[r]=dist[e]+node[i].v;if(!visit[r]){q.push(r);visit[r]=1;}}}}if(dist[ns]==-1)return 0;return 1;
}
void change()
{int minx,i;minx=INF;for(i=pre[ns];node[i].l!=0;i=pre[node[i].l]){minx=min(minx,node[i].f);}for(i=pre[ns];node[i].l!=0;i=pre[node[i].l]){node[i].f-=minx;node[i^1].f+=minx;ans+=minx*node[i].v;}
}
int main()
{int i,j;int ll,rr;while(~scanf("%d%d",&n,&k)){memset(head,-1,sizeof(head));num=0;int a;for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&a);ll=(i-1)*n+j;rr=ll+n*n;add(ll,rr,a,1);add(ll,rr,0,k-1);if(j<n){ll=(i-1)*n+j+n*n;rr=(i-1)*n+j+1;add(ll,rr,0,k);}if(i<n){ll=(i-1)*n+j+n*n;rr=i*n+j;add(ll,rr,0,k);}}}ll=n*n+n*n;rr=ll+1;ns=rr;ans=0;add(0,1,0,k);add(ll,rr,0,k);while(bfs())change();cout<<ans<<endl;}return 0;
}