题意： 一个数字矩阵，可以出发K次，每次可以从右边或者下面走，要求（在收益最大情况下）覆盖全图，不能则输出-1。（规则：每次跳一步的时候若格子数字相等则获得该数字的能量，每跳一步消耗距离的能量）。每个格子走且仅能走一次。

选<=K条路径，最优情况来覆盖全图。

显然用拆点为二分图。

一种解法：边（流量，费用）

源点向X部连边（1,0）Y部向汇点连边（1,0）X到Y，若能到，则有边（1，消耗-获得）。关键点（解决每个点都覆盖，恰好起到填补的作用）：在X部最上面添加一个点，源点连之（k,0）它向所有Y点连边（1,0）。跑最小费用最大流即可。

第二种：（感想zz1215提供的建图思路）

源点向X部连边（1,0）Y部向汇点连边（1,0）,Y到X，若能到，则有边（1，消耗-获得）(注意这里是回流)，每个点I-->I`有边（1，-w_inf），这里的w_inf为相对大数，只要保证该费用较“小”即可（相对其他费用，他是最廉价的，这样必优先流这条边。添加超级源点，向源点连边（K,0）。增广K次中，若一直增大，则取最大，否则到开始下降的时候要BREAK。（先曾后减的）。

PS:开始时候因为定位编号搞错有没有！编号（i,j）=i*m+j,而不是i*n+j！！！

图：

<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tPrC66O6PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#include //24ms #include #include #include #include using namespace std; int n,m,k; const int inf=0x3f3f3f3f; int a[25][25]; int head[500];int e[10000][4];int nume=0; void inline adde(int i,int j,int c,int w) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume][2]=c;e[nume++][3]=w; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume][2]=0;e[nume++][3]=-w; } int inq[500];int d[500]; bool spfa(int &sumcost) { for(int i=0;i<=2*n*m+3;i++) { inq[i]=0;d[i]=inf; } int minf=inf; queue q; int prv[300];int pre[300]; q.push(2*n*m+2); inq[2*n*m+2]=1; d[2*n*m+2]=0; while(!q.empty()) { int cur=q.front(); q.pop();inq[cur]=0; for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&d[v]>e[i][3]+d[cur]) { d[v]=e[i][3]+d[cur]; prv[v]=cur; pre[v]=i; if(!inq[v]) { q.push(v); inq[v]=1; } } } } if(d[2*n*m+1]==inf)return 0; int cur=2*n*m+1; while(cur!=2*n*m+2) { minf=min(minf,e[pre[cur]][2]); cur=prv[cur]; } cur=2*n*m+1; while(cur!=2*n*m+2) { e[pre[cur]][2]-=minf;e[pre[cur]^1][2]+=minf; cur=prv[cur]; } sumcost+=d[2*n*m+1]*minf; return 1; } int mincost() { int sum=0; while(spfa(sum)); return sum; } void init() { nume=0; for(int i=0;i<=2*n*m+3;i++) { head[i]=-1; } } int main() { int T; scanf("%d",&T); for(int iii=1;iii<=T;iii++) { scanf("%d%d%d",&n,&m,&k); init(); string s; for(int i=0;i >s; for(int j=0;j k) { printf("-1\n");continue; } for(int i=0;i %d:c:%d,w:%d\n",i,e[j][0],e[j][2],e[j][3]);*/ printf("%d\n",-mincost()); } return 0; }

方法二：

#include
  
              //31ms
#include
   
     #include
    
      #include
     
       using namespace std; int n,m,k; const int inf=0x3f3f3f3f; const int winf=100000; int a[25][25]; int head[500];int e[20001][4];int nume=0; void inline adde(int i,int j,int c,int w) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume][2]=c;e[nume++][3]=w; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume][2]=0;e[nume++][3]=-w; } int inq[500];int d[500]; bool spfa(long long &sumcost) { for(int i=0;i<=2*n*m+3;i++) { inq[i]=0;d[i]=inf; } int prv[500];int pre[500]; int minf=inf; queue
      
       q; q.push(n*m); inq[n*m]=1; d[n*m]=0; while(!q.empty()) { int cur=q.front(); q.pop(); inq[cur]=0; for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&d[v]>e[i][3]+d[cur]) { d[v]=e[i][3]+d[cur]; prv[v]=cur; pre[v]=i; if(!inq[v]) { q.push(v); inq[v]=1; } } } } if(d[2*n*m+1]==inf)return 0; int cur=2*n*m+1; while(cur!=n*m) { minf=min(minf,e[pre[cur]][2]); cur=prv[cur]; } cur=2*n*m+1; while(cur!=n*m) { e[pre[cur]][2]-=minf; e[pre[cur]^1][2]+=minf; cur=prv[cur]; } sumcost+=d[2*n*m+1]*(long long)minf; return 1; } long long mincost() { long long sum=0; long long lastsum=0; while(spfa(sum)) //变小的时候跳出 { if(lastsum>=-sum){return -lastsum;} lastsum=-sum; } return sum; } void init() { nume=0; for(int i=0;i<=2*n*m+3;i++) { head[i]=-1; } } int main() { int T; scanf("%d",&T); for(int iii=1;iii<=T;iii++) { scanf("%d%d%d",&n,&m,&k); init(); string s; for(int i=0;i
       
        >s; for(int j=0;j
        
         k) { printf("-1\n");continue; } for(int i=0;i
         
          %d:c:%d,w:%d\n",i,e[j][0],e[j][2],e[j][3]);*/ cout<<-mincost()-n*m*winf<