简要介绍一下如何构图 拆点：因为每个方格只取一次，但要走两遍，因此我们考虑对于矩阵中每个方格拆为两个节点，一个为流入点，记为 iii ；一个为流出 点，记为 iii '。连两条边从 i−>ii->ii−>i ’，两条容量都为 111 ，费用为 −g-g−g [ iii ][ jjj ]和 000 。 编号：这个大家有各自的习惯。我的题解中具体看我程序中的 hashinhashinhashin 和 hashouthashouthashout 函数和注释， hashinhashinhashin 用于编号我前文所提到 的 iii ， hashouthashouthashout 用于编号我前文所提到的 iii '。 连接节点：每个节点的 outoutout 连接它的右边和它下边节点的流入点，对于边界特殊处理一下， sss 连( 000 , 000 )的入点，( n−1n-1n−1 , n−1n-1n−1 )连 ttt 点。 这样构图跑一遍 spfaspfaspfa 的最小费用最大流就 OKOKOK 了。

看到这道题很容易想到动态规划，求一个矩阵最大权值路径算是家常便饭了 但是它要求输出的是两条路线和最大 这就有点伤脑筋了。。。 在做一条路线的时候我们是定义二维DP[i][j]DP[i][j]DP[i][j]，表示路线在(i,j)(i,j)(i,j)位置上所能获得的最大值 现在多了一条路线，多了两个状态，那我们再加两维让它变成四维DPDPDP和二维的时候差不多求解，这不就解决了嘛！ 定义DP[i][j][w][k]DP[i][j][w][k]DP[i][j][w][k]表示第一条路线在(i,j)(i,j)(i,j),第二条路线在(w,k)(w,k)(w,k)时的最大取值 使用四个forforfor循环(毕竟数据不大)

简单的DP。 状态设计：dpi,j,k,ldp_{i,j,k,l}dpi,j,k,l 表示第一次走到 (i,j)(i,j)(i,j)，第二次走到 (k,l)(k,l)(k,l) 的最大值。 转移方程就很显然了。 注意减去 (i,j)(i,j)(i,j) 与 (k,l)(k,l)(k,l) 重合的时候。 Code: