思路：
dp方法：
设dp[i][j][k][l]为两条没有交叉的路径分别走到(i，j)和(k，l)处最大价值。
则转移方程为
dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1])+map[i][j]+map[k][l];
若两点相同减去一个map[i][j]即可
费用流方法（可以扩展为k条路径，但时间复杂度较高）：
源点连接左上角点流量为k、费用为0，右下角点连接汇点流量为k、费用为0，所有点连接右边相邻和下边相邻点流量为k、费用为0，所有点拆点一条流量为1、费用为该
点价值，一条流量为k-1、费用为0。跑最大费用流即可
代码：
dp：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std; #define N 55 __int64 map[N][N];
__int64 dp[N][N][N][N];
int n, m; main()
{
int i, j, k, l;
int x, y, w;
while(scanf("%d %d",&n,&m)==){
memset(map,,sizeof(map));
memset(dp,,sizeof(dp));
for(i=;i<=n;i++){
for(j=;j<=m;j++){
scanf("%I64d",&map[i][j]);
}
}
for(i=;i<=n;i++){
for(j=;j<=m;j++){
for(k=;k<=n;k++){
for(l=;l<=m;l++){
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-][j][k-][l]);
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-][k-][l]);
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-][j][k][l-]);
dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j-][k][l-]);
dp[i][j][k][l]+=map[i][j]+map[k][l];
if(i==k&&j==l) dp[i][j][k][l]-=map[i][j];
}
}
}
}
printf("%I64d\n",dp[n][m][n][m]);
}
}
费用流：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std; #define N 205
#define M 1005
#define inf 999999999 struct MCF{//min_cost_flow
struct Edge{
int v, f, w, next;
Edge(){};
Edge(int a,int b,int c,int d){
v=a;f=b;w=c;next=d;
}
};
int n;
int head[N+];
Edge e[M*];
int nume;
int src, sink; void init(int st, int end,int nn){//初始化
src=st;sink=end;n=nn;
memset(head,,sizeof(head));
nume=;
} void addedge(int u,int v,int c,int w){
e[++nume]=Edge(v,c,w,head[u]);
head[u]=nume;
e[++nume]=Edge(u,,-w,head[v]);
head[v]=nume;
} queue<int>Q;
bool visited[N];
int dis[N];
int prev[N], pree[N]; bool findpath(){ while(!Q.empty()) Q.pop();
Q.push(src);
for(int i=;i<=n;i++) dis[i]=-;
dis[src]=;
visited[src]=true;
while(!Q.empty()){
int u=Q.front();Q.pop();visited[u]=false;
for(int i=head[u];i;i=e[i].next){
if(e[i].f>&&dis[u]+e[i].w>dis[e[i].v]){
dis[e[i].v]=dis[u]+e[i].w;
prev[e[i].v]=u;
pree[e[i].v]=i;
if(!visited[e[i].v]){
Q.push(e[i].v);
visited[e[i].v]=true;
}
}
}
}//printf("111111\n");
if(dis[sink]>) return true;
else return false;
} int solve(){ int u=sink;
int flow=inf;
while(u!=src){
if(e[pree[u]].f<flow) flow=e[pree[u]].f;
u=prev[u];
}
u=sink;
while(u!=src){
e[pree[u]].f-=flow;
e[pree[u]^].f+=flow;
u=prev[u];
} return dis[sink]*flow;
} int mincostflow(){
int ans=;
while(findpath()){
ans+=solve();
}
return ans;
}
}mcf; int n;
int map[][]; int x, y, w; main()
{
int i, j, k;
while(scanf("%d",&n)==){
memset(map,,sizeof(map));
while(){ scanf("%d %d %d",&x,&y,&w);
if(x==&&y==&&w==) break;
map[x][y]=w;
}
mcf.init(,n*n*+,n*n*+);
mcf.addedge(,,,);
mcf.addedge(n*n*,n*n*+,,);
int temp=;
for(i=;i<=n;i++){
for(j=;j<=n;j++){
mcf.addedge(temp,temp+n*n,,map[i][j]);
mcf.addedge(temp,temp+n*n,,);
if(i<n) mcf.addedge(temp+n*n,temp+n,,);
if(j<n) mcf.addedge(temp+n*n,temp+,,);
temp++;
}
}
printf("%d\n",mcf.mincostflow());
}
}