题意：
卡卡有一个矩阵，从左上角走到右下角，卡卡每次只能向右或者向下。矩阵里边都是不超过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=-1; //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],0,b,c,v},e2={V[b],0,a,0,-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=1;i<=n;i++) for(int j=1;j<=n;j++){ int tmp; scanf("%d",&tmp); addedge((i-1)*n+j,n*n+(i-1)*n+j,-tmp,1); if(j<n){ addedge(n*n+(i-1)*n+j,(i-1)*n+j+1,0); addedge((i-1)*n+j,(i-1)*n+j+1,0); } if(i<n){ addedge(n*n+(i-1)*n+j,i*n+j,0); addedge((i-1)*n+j,i*n+j,0); } } S=0,T=n*n*2+1; addedge(n*n,T,0); addedge(S,1,0,k); addedge(n*n*2,T,0); } bool SPFA(){ int u,v; for(u=S;u<=T;u++){ sp[u]=INF; } queue<int>q; prev[S]=-1; q.push(S); sp[S]=0; vis[S]=1; while(!q.empty()){ u=q.front(); vis[u]=0; q.pop(); for(edge *k=V[u];k;k=k->next){ v=k->t; if(k->c>0&&sp[u]+k->v<sp[v]){ sp[v]=sp[u]+k->v; prev[v]=u; path[v]=k; if(vis[v]==0){ vis[v]=1; q.push(v); } } } } return sp[T]!=INF; } int argument(){ int i,cost=INF,flow=0; edge *e; for(i=T;prev[i]!=-1;i=prev[i]){ e=path[i]; if(e->c<cost)cost=e->c; } for(int i=T;prev[i]!=-1;i=prev[i]){ e=path[i]; e->c-=cost;e->op->c+=cost; flow+=e->v*cost; } return flow; } int maxcostflow(){ int Flow=0; while(SPFA()){ Flow+=argument(); } return Flow; } int main(){ init(); printf("%d ",-maxcostflow()); return 0; }