一、题目描述

:::info 设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:
A
0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
B
某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。

输入格式

输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。

输出格式

只需输出一个整数，表示 2 条路径上取得的最大的和。

输入输出样例

输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出
67 :::

二、深度优先搜索

首先这道题用两遍dp是不行的，有的情况下会出现 wrong answer 的情况。由于数据的量级不大，我直接用dfs 的方式搜索出最终答案。

  1. // 方格取数
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<vector>
  5. using namespace std;
  7. #define MAX(A,B) (((A)>(B))?(A):(B))
  8. #define Init 0
  9. #define First 1
  10. #define Second 2
  11. #define None 3
  12. struct route_num{
  13.     int _value; 
  14.     route_num(): _value(0) {}
  15.     route_num(int v): _value(v) {}
  16. };
  17. route_num operator+(const route_num & r, const int & i){
  18.     return (r._value+i>3)?3:(r._value+i);
  19. } 
  20. bool operator==(const route_num & r, const route_num & s){
  21.     return r._value==s._value;
  22. }
  23. bool operator==(const route_num & r, const int & s){
  24.     return r._value==s;
  25. }
  26. struct coordinate{
  27.     int i;
  28.     int j;
  29.     int value;
  30.     route_num curr_route;
  31.     coordinate(): i(0), j(0), value(0), curr_route() {}
  32.     coordinate(int ii, int jj, int vv): i(ii), j(jj), value(vv), curr_route() {}
  33. };
  34. bool operator==(const coordinate & c1, const coordinate & c2){
  35.     return (c1.i==c2.i)&&(c1.j==c2.j);
  36. }
  37. bool i_less(const coordinate & c1, const coordinate & c2){
  38.     return (c1.i<c2.i);
  39. }
  40. bool j_less(const coordinate & c1, const coordinate & c2){
  41.     return (c1.j<c2.j);
  42. }
  44. struct route{
  45.     vector<coordinate> coordinate_list;
  46.     bool insert(coordinate &c){
  47.         if(coordinate_list.size()==0){
  48.             coordinate_list.push_back(c);
  49.             return true;
  50.         }
  51.         int c_pos = coordinate_list.size();
  52.         for(int i=0; i<coordinate_list.size(); i++){
  53.             if(!i_less(coordinate_list[i], c)){
  54.                 c_pos = i+1;    
  55.             }
  56.         }    
  57.         if(c.j>=coordinate_list[c_pos-1].j){
  58.             coordinate_list.insert(coordinate_list.begin()+c_pos, c);
  59.             return true;
  60.         }
  61.         return false;
  62.     }
  63.     bool pop(coordinate &c){
  64.         bool done = false;
  65.         for(int i=0; i<coordinate_list.size(); i++){
  66.             if(coordinate_list[i]==c){
  67.                 coordinate_list.erase(coordinate_list.begin()+i);
  68.                 done = true;
  69.                 break;
  70.             }
  71.         }
  72.         return done;
  73.     }
  74.     void display(){
  75.         printf("-------------\n");
  76.         for(auto c: coordinate_list){
  77.             printf("i=%d, j=%d, value=%d\n", c.i, c.j, c.value);
  78.         }
  79.         printf("--------------\n");
  80.     }
  81. };
  83. int Find_Max_Route(vector<coordinate> &v){
  84.     route route_a,route_b;
  85.     int max_value = 0;
  86.     int value = 0;
  87.     int i=0;
  88.     while(i>=0){
  89.         if(i==v.size()){
  90.             i--;
  91.         }
  92.         if(v[i].curr_route == First){
  93.             if(route_a.pop(v[i])){value -= v[i].value;}
  94.         } else if(v[i].curr_route == Second){
  95.             if(route_b.pop(v[i])){value -= v[i].value;}
  96.         } else if(v[i].curr_route == None){
  97.             v[i].curr_route = Init;
  98.             i--;
  99.             continue;
  100.         }
  101.         v[i].curr_route = v[i].curr_route + 1;
  102.         if(v[i].curr_route == First){
  103.             if(route_a.insert(v[i])){
  104.                 //成功安置
  105.                 value += v[i].value;
  106.                 max_value = MAX(max_value, value);
  107.                 i++;
  108.             }
  109.         } else if(v[i].curr_route == Second){
  110.             if(route_b.insert(v[i])){
  111.                 //成功安置
  112.                 value += v[i].value;
  113.                 max_value = MAX(max_value, value);
  114.                 i++;
  115.             }
  116.         } else{
  117.             i++;
  118.         }
  119.     }
  120.     return max_value;
  121. }
  123. int main(){
  124.     // freopen("lg_p1004.test_data", "r", stdin);
  125.     int n;
  126.     scanf("%d", &n);
  127.     vector<coordinate> ground;
  129.     int i, j, k;
  130.     while(scanf("%d %d %d", &i, &j, &k)){
  131.         if(i==0&&j==0&&k==0){
  132.             break;
  133.         }
  134.         ground.push_back(coordinate(i,j,k));
  135.     }
  137.     int a = Find_Max_Route(ground);
  138.     printf("%d\n", a);
  140.     return 0;
  141. }

三、四维DP

结果看其他人的题解时，才发现这还是一道 dp 题，只不过并不是对二维数组做两遍 dp, 而是对一个四维的数组做一遍 dp。大概思路如下：
dp[i][j][k][l] 代表 第一条路径抵达点 ( i , j )，第二条路径抵达点 ( k , l ) 时的最优解。因为在只考虑一条线路的时候，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。所以我们可以很自然地得到两条线路同时 dp 的状态转移方程：
dp[i][j][k][l] = max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1], dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])
且当 ( i , j ) 等于 ( k , l ) 时，我们要再减去 value[i][j]。因为题目中存放在方格中的数只能被取一次。

完整代码如下：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int f[12][12][12][12],a[12][12],n,x,y,z;
  6. int main() {
  7.     cin>>n>>x>>y>>z;
  8.     while(x!=0||y!=0||z!=0){
  9.         a[x][y]=z;
  10.         cin>>x>>y>>z;
  11.     }
  12.     for(int i=1;i<=n;i++){
  13.         for(int j=1;j<=n;j++){
  14.             for(int k=1;k<=n;k++){
  15.                 for(int l=1;l<=n;l++){
  16.                     f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
  17.                     if(i==k&&l==j)f[i][j][k][l]-=a[i][j];
  18.                 }
  19.             }
  20.         }
  21.     }
  22.     cout<<f[n][n][n][n];
  23.     return 0;
  24. }

四、费用流

还看到了一个费用流的解法，之前没接触过相关的概念，实在是看不懂代码里面在写什么，先摘抄过来 mark 一下。
（ 本节内容 copy 自 https://www.luogu.com.cn/blog/chenyy/solution-p1004 ）

看了下题解还没有spfa的费用流解法，就自己发一份了。来自一位不会动规的蒟蒻。 简要介绍一下如何构图

  1. 拆点：因为每个方格只取一次，但要走两遍，因此我们考虑对于矩阵中每个方格拆为两个节点，一个为流入点，记为i；一个为流出点，记为i’。连两条边从i->i’，两条容量都为1，费用为-g[i][j]和0。
  2. 编号：这个大家有各自的习惯。我的题解中具体看我程序中的hashin和hashout函数和注释，hashin用于编号我前文所提到的i，hashout用于编号我前文所提到的i’。
  3. 连接节点：每个节点的out连接它的右边和它下边节点的流入点，对于边界特殊处理一下，s连(0,0)的入点，(n-1,n-1)连t点。

这样构图跑一遍spfa的最小费用最大流就OK了。

  1. #include <cstdio> 
  2. #include <cstring> 
  3. #include <queue> 
  4. #define INF 0x7f7f7f7f 
  5. using namespace std; 
  6. struct Edge{     
  7.     int u;//大多数算法在邻接表中并不需要这个，但费用流比较例外     
  8.     int v;     
  9.     int f;//残量      
  10.     int c;//费用      
  11.     int next; 
  12. }e[850];//网络流的题目都要记得边数开两倍，因为还有反向弧 
  13. int head[170]; 
  14. int n,m,s,t; 
  15. int ecnt = 0; 
  16. inline void AddEdge(int _u,int _v,int _f,int _c) {     
  17.     e[ecnt].next = head[_u];     
  18.     head[_u] = ecnt;     
  19.     e[ecnt].u = _u;     
  20.     e[ecnt].v = _v;     
  21.     e[ecnt].f = _f;     
  22.     e[ecnt].c = _c;     
  23.     ecnt++; 
  24. }
  25. inline void Add(int _u,int _v,int _f,int _c) {     
  26.     AddEdge(_u,_v,_f,_c);     
  27.     AddEdge(_v,_u,0,-_c); 
  28. } 
  29. int dis[170]; 
  30. bool inq[170]; 
  31. int pre[170]; 
  32. bool SPFA() {     
  33.     queue <int> q;     
  34.     q.push(s);     
  35.     memset(dis,0x7f,sizeof(dis));     
  36.     memset(inq,0,sizeof(inq));     
  37.     memset(pre,-1,sizeof(pre));     
  38.     inq[s] = true;     
  39.     dis[s] = 0;     
  40.     while (!q.empty()) {         
  41.         int cur = q.front();         
  42.         q.pop();         
  43.         inq[cur] = false;         
  44.         for (int i = head[cur];i != -1;i = e[i].next) {             
  45.             if (e[i].f != 0 && dis[e[i].v] > dis[cur] + e[i].c) {                 
  46.                 dis[e[i].v] = dis[cur] + e[i].c;                 
  47.                 pre[e[i].v] = i;                 
  48.                 if (!inq[e[i].v]) {                     
  49.                     inq[e[i].v] = true;                     
  50.                     q.push(e[i].v);                 
  51.                 }             
  52.             }         
  53.         }     
  54.     }     
  55.     return dis[t] != INF; 
  56. } 
  57. void MICMAF(int &flow,int &cost) {     
  58.     flow = 0;     
  59.     cost = 0;     
  60.     while (SPFA()) {         
  61.         int minF = INF;         
  62.         for (int i=pre[t];i != -1;i=pre[e[i].u]) minF = min(minF,e[i].f);         
  63.         flow += minF;         
  64.         for (int i=pre[t];i != -1;i=pre[e[i].u]) {             
  65.             e[i].f -= minF;             
  66.             e[i^1].f += minF;         
  67.         }         
  68.         cost += dis[t] * minF;     
  69.     } 
  70. } 
  71. /* 节点编号规则：
  72. 源点：0 
  73. 矩阵节点(入)：n*x+y+1 
  74. 矩阵节点(出)：n*n+n*x+y+1 
  75. 汇点：2*n*n+1 */
  76. int g[10][10]; 
  77. inline int hashin(int x,int y) {     
  78.     return n*x+y+1; 
  79. }
  80. inline int hashout(int x,int y) {     
  81.     return n*n + n * x + y + 1; 
  82. }
  83. int main() {     
  84.     memset(head,-1,sizeof(head));     
  85.     scanf("%d",&n);     
  86.     int x,y,v;     
  87.     while (scanf("%d%d%d",&x,&y,&v) == 3) {         
  88.         if (x == 0 && y == 0 && v == 0) 
  89.             break;         
  90.         x --;         
  91.         y --;         
  92.         g[x][y] = v;     
  93.     }     
  94.     s = 0;     
  95.     t = 2 * n * n + 1;     
  96.     Add(s,1,2,0);     
  97.     Add(2*n*n,t,2,0);     
  98.     for (int i=0;i<n;i++)         
  99.         for (int j=0;j<n;j++) {             
  100.             int in = hashin(i,j);             
  101.             int out = hashout(i,j);             
  102.             Add(in,out,1,0);//邻接表中后插入的先遍历，卡常，f=1是因为只可能再经过一次     
  103.             Add(in,out,1,-g[i][j]);             
  104.             if (i != n - 1) 
  105.                 Add(out,hashin(i+1,j),2,0);             
  106.             if (j != n - 1) 
  107.                 Add(out,hashin(i,j+1),2,0);         
  108.         }     
  109.     int f,c;     
  110.     MICMAF(f,c);     
  111.     printf("%d\n",-c);     
  112.     return 0; 
  113. }