一遍的话秩序要dp就好，但是这里要删去点。此题可以转化为最小费用流。开始我想了半天纠结怎么处理到过一次后值变0，看了书之后发现拆点解决了这个问题。
对于点t，拆为t-->t'，容量为1，费用为负的矩阵的值，那就解决了只能一次。如果2个点连通，s-->t,就相连,s-->t,s-->t',t'->s',t'->s，容量为无穷，费用0。
然后费用流，得到的值取负即可。
#include<stdio.h> #include<string.h> #include<queue> #define INF 99999999 using namespace std; const int maxn = 5560; struct mp { int v; int cnt; } map[55][55]; struct node { int to; int v; int cost; int flag; int next; } edge[maxn*maxn/2]; int pre[maxn],fpre[maxn],index,head[maxn],dis[maxn],n,k,N; int ok(int x1,int y1,int x2,int y2) { if(x1>=n||y1>=n||x2>=n||y2>=n) return 0; return 1; } void add(int x,int y,int v,int cost) { edge[index].to=y; edge[index].v=v; edge[index].cost=cost; edge[index].flag=index+1; edge[index].next=head[x]; head[x]=index++; edge[index].to=x; edge[index].v=0; edge[index].cost=-cost; edge[index].flag=index-1; edge[index].next=head[y]; head[y]=index++; } int spfa(int S,int T) { int vis[maxn],i; queue<int>q; memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); for(i=0; i<=T; i++) dis[i]=INF; dis[S]=0; vis[S]=1; pre[S]=0; q.push(S); while(!q.empty()) { int t=q.front(); q.pop(); vis[t]=0; for(i=head[t]; i!=-1; i=edge[i].next) { if(edge[i].v&&dis[edge[i].to]>dis[t]+edge[i].cost) { dis[edge[i].to]=dis[t]+edge[i].cost; if(!vis[edge[i].to]) { vis[edge[i].to]=1; q.push(edge[i].to); } pre[edge[i].to]=t; fpre[edge[i].to]=i; } } } //printf("1 "); if(dis[T]>=INF)return 0; return 1; } void MCMF(int S,int T) { int i; int ans=0; while(spfa(S,T)) { int minflow=INF; for(i=T; i!=0; i=pre[i]) { if(minflow>edge[fpre[i]].v) minflow=edge[fpre[i]].v; } ans+=dis[T]*minflow; for(i=T; i!=0; i=pre[i]) { edge[fpre[i]].v-=minflow; edge[edge[fpre[i]].flag].v+=minflow; } } printf("%d ",-ans); } int main() { int i,j; while(~scanf("%d%d",&n,&k)) { N=n*n; index=1; memset(head,-1,sizeof(head)); int cnt=0; for(i=0; i<n; i++) for(j=0; j<n; j++) { map[i][j].cnt=++cnt; scanf("%d",&map[i][j].v); } for(i=0; i<n; i++) { for(j=0; j<n; j++) { add(map[i][j].cnt,map[i][j].cnt+N,1,-map[i][j].v); if(ok(i,j,i,j+1)) { add(map[i][j].cnt,map[i][j+1].cnt,INF,0); add(map[i][j].cnt,map[i][j+1].cnt+N,INF,0); add(map[i][j].cnt+N,map[i][j+1].cnt,INF,0); add(map[i][j].cnt+N,map[i][j+1].cnt+N,INF,0); } if(ok(i,j,i+1,j)) { add(map[i][j].cnt,map[i+1][j].cnt,INF,0); add(map[i][j].cnt,map[i+1][j].cnt+N,INF,0); add(map[i][j].cnt+N,map[i+1][j].cnt,INF,0); add(map[i][j].cnt+N,map[i+1][j].cnt+N,INF,0); } } } add(0,1,k,0); add(map[n-1][n-1].cnt,2*N,k,0); int S=0,T=n*n*2; MCMF(S,T); } }