本文共 2706 字，大约阅读时间需要 9 分钟。

这里必须要简单说一下题目：

求K次矩阵左上至右下的路径和最大，每次只能向下或向右走，每个单元格的值只能取一次。

第一眼直接敲了K次DP，直接WA。

$为什么DP不可以？$

dp合理的基础是每次路径最优，则总体最优，基于贪心策略。

但对于矩阵，总觉得哪里对不上，肯定有反例。

于是：

4 3

这个DP跑出32，最小费用最大流跑出34

K次DP对于网络流缺乏全局意识。

具体解法：

由于是点权值，则常用思路拆点。

$实现最小费用最大流：$

1，SPFA求S到T的最小费用路。（这里求最大和，则费用转为负值）

用SPFA不能出现负权值回路，拆点时要注意，去边费用负值，回边费用正值。

$注：$ 忘了哪里看到，SPFA算法每个点平均入队2次，复杂度O(2*M)

2，DFS把SPFA找到路径修改流量即可。

// ShellDawn// POJ3422// No.29#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;//#define maxn 55int N,K;int S,T;struct Edge{ int from; int to; int f; int w; int rvs; int pre;};Edge E[maxn*maxn*10];int pre[maxn*maxn*2];int cnt;int dis[maxn*maxn*2];int path[maxn*maxn*2];int visited[maxn*maxn*2];int ans;void addE(int from,int to,int f,int w,int rvs){ E[cnt].from = from; E[cnt].to = to; E[cnt].f = f; E[cnt].w = w; E[cnt].rvs = rvs; E[cnt].pre = pre[from]; pre[from] = cnt++;}bool SPFA(int s){ MM(dis,INF);MM(path,0);MM(visited,0); queue
         
           q; q.push(s); dis[s] = 0; while(!q.empty()){ int now = q.front(); //printf("<%d>",now); q.pop(); visited[now] = 0; for(int i=pre[now];i!=0;i=E[i].pre){ if(E[i].f > 0 && dis[now] + E[i].w < dis[E[i].to]){ path[E[i].to] = i; // 索引边 dis[E[i].to] = dis[now] + E[i].w; if(visited[E[i].to] == 0){ visited[E[i].to] = 1; q.push(E[i].to); } } } } //puts(""); //for(int i=0;i<=N*N*2+1;i++) printf("%d ",dis[i]); //puts(""); if(dis[T] == INF) return false; return true;}int DFS(){ int loc = path[T]; // 边索引 int minflow = INF; while(loc!=0){ //printf("<%d->%d %d>\n",E[loc].from,E[loc].to,E[loc].f); //getchar(); minflow = min(minflow,E[loc].f); loc = path[E[loc].from]; } int minw = 0; loc = path[T]; while(loc!=0){ E[loc].f -= minflow; E[E[loc].rvs].f += minflow; minw += E[loc].w; loc = path[E[loc].from]; } return minw;}int main(){ while(~scanf("%d%d",&N,&K)){ int M = N*N; S = 0; T = M+M+1; cnt = 1; MM(pre,0); // 源点 int t = cnt; addE(S,1,K,0,t+1); addE(1,S,0,0,t); // end // 拆点 for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ int w; scanf("%d",&w); int a = N*(i-1) + j; // 入 int b = a + M; // 出 t = cnt; addE(a,b,1,-w,t+1); // 将正值转为负值，方便求最短路 addE(b,a,0,w,t); addE(a,b,INF,0,t+1); addE(b,a,0,0,t+1); int c = a + N; // 下 int d = a + 1; // 右 if(i!=N){ t = cnt; addE(b,c,INF,0,t+1); addE(c,b,0,0,t); } if(j!=N){ t = cnt; addE(b,d,INF,0,t+1); addE(d,b,0,0,t); } } } //end // 汇点 t = cnt; addE(M+M,T,INF,0,t+1); addE(T,M+M,0,0,t); //end //print(); ans = 0; while(SPFA(S)) ans += DFS(); printf("%d\n",-ans); } return 0;}
         
        
       
      
     
    
   

转载地址：http://cnwji.baihongyu.com/