题意： 一个数字矩阵，可以出发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！！！

图：

代码：

#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<