题意：
卡卡有一个矩阵，从左上角走到右下角，卡卡每次只能向右或者向下。矩阵里边都是不超过1000的正整数，卡卡走过的元素会变成0，问卡卡可以走k次，问卡卡最多能积累多少和。
思路：
最小费用最大流的题目。
建图自己没想出来，看了大神的建边，把每个点分解成两个点，一个代表进入一个代表出去，然后每个进入和每个出去连边，容量是1价值是这个点的矩阵的数值。然后因为可以不进去，所以起点要和别的矩阵元素的起点建边，终点也要和别的矩阵矩阵元素的起点建边，最后跑下最小费用最大流。
这题最右下角的矩阵元素需要特殊处理下.然后源点和左上角的矩阵元素的起点连边，容量为k，权值是0.
#include<stdio.h>
#include<queue>
#define MAXN 6003
#define MAXM 10002*4
#define INF 10000000
using namespace std;
//起点编号必须最小，终点编号必须最大
bool vis[MAXN]; //spfa中记录是否在队列里边
struct edge{
edge *next,*op; //op是指向反向边
int t,c,v; //t下一个点编号，c容量，v权值
}ES[MAXM],*V[MAXN]; //ES边静态邻接表，V点的编号
int N,M,S,T,EC=-; //S源点最小，T汇点最大，EC当前边数
int demond[MAXN],sp[MAXN],prev[MAXN]; //spSPFA中记录距离，prev记录上一个点路径
edge *path[MAXN]; //与prev同步记录，记录到上一条边
void addedge(int a,int b,int v,int c=INF){
edge e1={V[a],,b,c,v},e2={V[b],,a,,-v};
ES[++EC]=e1;V[a]=&ES[EC];
ES[++EC]=e2;V[b]=&ES[EC];
V[a]->op=V[b];V[b]->op=V[a];
}
void init(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
int tmp;
scanf("%d",&tmp);
addedge((i-)*n+j,n*n+(i-)*n+j,-tmp,);
if(j<n){
addedge(n*n+(i-)*n+j,(i-)*n+j+,);
addedge((i-)*n+j,(i-)*n+j+,);
}
if(i<n){
addedge(n*n+(i-)*n+j,i*n+j,);
addedge((i-)*n+j,i*n+j,);
}
}
S=,T=n*n*+;
addedge(n*n,T,);
addedge(S,,,k);
addedge(n*n*,T,);
}
bool SPFA(){
int u,v;
for(u=S;u<=T;u++){
sp[u]=INF;
}
queue<int>q;
prev[S]=-;
q.push(S);
sp[S]=;
vis[S]=;
while(!q.empty()){
u=q.front();
vis[u]=;
q.pop();
for(edge *k=V[u];k;k=k->next){
v=k->t;
if(k->c>&&sp[u]+k->v<sp[v]){
sp[v]=sp[u]+k->v;
prev[v]=u;
path[v]=k;
if(vis[v]==){
vis[v]=;
q.push(v);
}
}
}
}
return sp[T]!=INF;
}
int argument(){
int i,cost=INF,flow=;
edge *e;
for(i=T;prev[i]!=-;i=prev[i]){
e=path[i];
if(e->c<cost)cost=e->c;
}
for(int i=T;prev[i]!=-;i=prev[i]){
e=path[i];
e->c-=cost;e->op->c+=cost;
flow+=e->v*cost;
}
return flow;
}
int maxcostflow(){
int Flow=;
while(SPFA()){
Flow+=argument();
}
return Flow;
}
int main(){
init();
printf("%d\n",-maxcostflow());
return ;
}