问题分析

我们有一个数字梯形：

• 第 $1$ 行有 $m$ 个数字
• 第 $i$ 行有 $m + i - 1$ 个数字
• 从顶部到底部可以走左下或右下方向
• 要找 $m$ 条路径，使得路径上数字总和最大

三种规则：

1. 路径互不相交：节点和边都不能重复
2. 仅在数字结点处相交：节点可以重复，边不能重复
3. 允许在数字结点相交或边相交：节点和边都可以重复

---

通用建模思路

将梯形中的每个数字位置看作图中的一个节点，用费用流求解：

• 每个节点的数字作为费用
• 通过容量限制来控制路径的相交规则
• 源点连接第一行的 $m$ 个节点
• 最后一行的节点连接汇点

---

规则1：路径互不相交

建图方法

1. 拆点：将每个节点 $u$ 拆成 $u_{in}$ 和 $u_{out}$，连边容量 $1$，费用 = 该节点的数字值
2. 移动边：从 $u_{out}$ 向它左下和右下的节点的 $u_{in}$ 连边，容量 $1$，费用 $0$
3. 源点：向第一行 $m$ 个节点的 $u_{in}$ 连边，容量 $1$，费用 $0$
4. 汇点：从最后一行所有节点的 $u_{out}$ 向汇点连边，容量 $1$，费用 $0$

原理

• 拆点容量为 $1$ 保证每个节点最多被一条路径使用
• 边容量为 $1$ 保证边不被重复使用
• 这样就保证了路径完全不相交

---

规则2：仅在数字结点处相交

建图方法

1. 拆点：每个节点 $u$ 拆成 $u_{in}$ 和 $u_{out}$，连边容量 $\infty$，费用 = 该节点的数字值
2. 移动边：从 $u_{out}$ 向它左下和右下的节点的 $u_{in}$ 连边，容量 $1$，费用 $0$
3. 源点：向第一行 $m$ 个节点的 $u_{in}$ 连边，容量 $1$，费用 $0$
4. 汇点：从最后一行所有节点的 $u_{out}$ 向汇点连边，容量 $\infty$，费用 $0$

原理

• 拆点容量 $\infty$ 允许节点被多条路径使用
• 边容量为 $1$ 保证边不被重复使用
• 这样路径可以在节点相交，但边不重复

---

规则3：允许在数字结点相交或边相交

建图方法

1. 拆点：每个节点 $u$ 拆成 $u_{in}$ 和 $u_{out}$，连边容量 $\infty$，费用 = 该节点的数字值
2. 移动边：从 $u_{out}$ 向它左下和右下的节点的 $u_{in}$ 连边，容量 $\infty$，费用 $0$
3. 源点：向第一行 $m$ 个节点的 $u_{in}$ 连边，容量 $1$，费用 $0$
4. 汇点：从最后一行所有节点的 $u_{out}$ 向汇点连边，容量 $\infty$，费用 $0$

原理

• 所有容量都是 $\infty$（除了源点出发的边）
• 允许节点和边都被多条路径使用
• 这样路径可以完全自由相交

---

样例验证

输入：

2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

梯形结构：

第1行: 2   3
第2行: 3   4   5  
第3行: 9   10  9   1
第4行: 1   1   10  1   1
第5行: 1   1   10  12  1   1

规则1结果：66
规则2结果：75
规则3结果：77

随着限制放宽，最大总和增加，因为可以重复利用高价值的节点。

---

算法步骤

对每种规则：

1. 根据规则建立对应的网络流图
2. 运行最大费用最大流算法（将费用取负值或用支持负费用的算法）
3. 输出最大流值为 $m$ 时的最大费用

---

复杂度分析

• 节点数：$O(mn)$，最多 $20 \times 20 = 400$ 个原始节点，拆点后约 $800$ 个
• 边数：$O(mn)$，每个节点最多2条出边
• 使用费用流算法（如SSP）：在这样规模下完全可行

---

总结

这道题通过拆点和容量控制来精确描述不同的路径相交规则：

• 规则1：节点容量1，边容量1 → 完全不相交
• 规则2：节点容量∞，边容量1 → 节点可交，边不交
• 规则3：节点容量∞，边容量∞ → 完全自由相交

展示了网络流在路径规划问题中的强大建模能力。