数字梯形问题

题目解析

这个问题是网络流（网络流二十四题之一）中的经典建模题。它考察了如何通过微调容量约束来表达离散数学中的不同相交规则。

🧠 离散数学：本质理解

1. 算子映射：路径与流量的等价性

我们将“ $m$ 条路径”映射为流网络中从源点到汇点的 $m$ 单位流量。梯形中的每一个数字节点 $V_{i,j}$ 都蕴含着两个属性：通行能力（Capacity）和收益（Cost/Weight）。

2. 数学推导：约束条件的逻辑化

设 $f(e)$ 为边 $e$ 上的流量， $c(v)$ 为节点 $v$ 的容量限制。三种规则可以形式化为不同的约束算子：

规则 1（点不相交）： $\forall v \in V, \sum f(in\_v) \le 1$ 且 $\forall e \in E, f(e) \le 1$ 。
- 映射：拆点 $In \to Out$ ，边容量为 $1$ ，费用为数字值。
规则 2（点可交，边不可交）： $\forall v \in V, \sum f(in\_v) \le m$ 且 $\forall e \in E, f(e) \le 1$ 。
- 映射：节点容量设为 $\infty$ （或 $m$ ），边容量设为 $1$ 。
规则 3（点边均可交）： $\forall v \in V, \sum f(in\_v) \le m$ 且 $\forall e \in E, f(e) \le m$ 。
- 映射：节点容量与边容量均设为 $\infty$ 。

3. 思维模版：收益的累加逻辑

注意：本题要求的是“ $m$ 条路径的数字总和”。这意味着如果两条路径经过同一个点，该点的数值会被计算两次。这与“方格取数”中数值取走变 $0$ 的逻辑不同。在这里，费用的产生是伴随流量的，即每单位流量经过节点 $V_{i,j}$ ，都会产生一次 $Weight(V_{i,j})$ 的贡献。

🛠️ 网络流建模

节点设计

源点 $S$ ，汇点 $T$ 。
拆点：每个位置 $(i, j)$ 拆为 $In(i,j)$ 和 $Out(i,j)$ 。

三种规则的连边策略

规则	内部边 In→Out	外部边 Out→Innext	说明
规则 1	容量 $1$ , 费用 $-val$	容量 $1$ , 费用 $0$	强制点和边都只用一次。
规则 2	容量 $\infty$ , 费用 $-val$	容量 $1$ , 费用 $0$	点可多人经过，边只能过一人。
规则 3	容量 $\infty$ , 费用 $-val$	容量 $\infty$ , 费用 $0$	点和边均无限制。

建模的理解

我们分三步来彻底拆解这个规则的数学本质和物理实现。

1. 数学公式的物理意义

公式： $\forall v \in V, \sum f(in\_v) \le 1$

$\forall v \in V$ ：对于图中的每一个节点（对应梯形中的每一个数字）。
$\sum f(in\_v)$ ：表示“流入这个节点的所有流量之和”。
$\le 1$ ：是一个硬性阈值。

直观理解：

想象这个数字节点是一个独木桥。

如果有两条路径想同时经过这个节点，那么流入流量 $\sum f = 1 + 1 = 2$ ，这就违反了 $\le 1$ 的约束。

这个公式本质上是用流量守恒（Flow Conservation）语言描述了“互斥性（Mutually Exclusive）”。

2. 为什么要拆点？（Logic Jump）

你可能会问：“我直接把连接节点的边的容量设为 1 不行吗？”

思维陷阱演示：

假设节点 $B$ 有两个入度（来自 $A, C$ ）和两个出度（去往 $D, E$ ）。

如果我们只限制外部边的容量为 1：

$A \to B$ (流 1)
$C \to B$ (流 1)
$B \to D$ (流 1)
$B \to E$ (流 1)

此时，四条边的流量都满足 $\le 1$ ，但是节点 $B$ 被经过了两次（一次是从 $A$ 穿过 $B$ 到 $D$ ，另一次是从 $C$ 穿过 $B$ 到 $E$ ）。

这违反了“点不相交（节点只能用一次）”的规则。

结论：标准网络流算法（Dinic/ISAP/SPFA-Cost）只能限制**边（Edge）的流量，无法直接限制点（Vertex）**的流量。

3. 拆点：将“点限制”降维为“边限制”

为了解决上述问题，我们引入拆点（Node Splitting）技术。这是一个离散数学中的同构映射。

映射过程

我们将物理空间的一个点 $u$ ，分裂为逻辑空间的两个点 $u_{in}$ 和 $u_{out}$ ，并用一条有向边连接它们。

物理意义：这条新产生的边 $(u_{in} \to u_{out})$ 代表了“穿过节点 $u$ 内部的过程”。
容量控制：我们将这条“内部边”的容量设为 1。
- 无论外部有多少流量涌入 $u_{in}$ ，能通过中间这条“独木桥”到达 $u_{out}$ 的流量只有 1。
费用承载：数字梯形中，只有经过这个点，才能获得这个数字的收益。因此，我们将收益（权值）绑定在这条“内部边”上。

数学证明

流守恒：流入 $u_{in}$ 的总流量必须等于流过 $(u_{in} \to u_{out})$ 的流量（因为没有其他出口）。
容量限制： $f(u_{in} \to u_{out}) \le 1$ 。
推导： $\sum f(into\_u_{in}) = f(u_{in} \to u_{out}) \le 1$ 。

这完美复现了题目要求的 $\sum f(in\_v) \le 1$ 。

4. 总结：规则与实现的对应表

题目语言	离散数学逻辑	网络流实现 (C++ Code)
点不相交	节点是互斥资源	内部边 $(u_{in} \to u_{out})$ 容量 = 1
边不相交	路径段是互斥资源	外部边 $(u_{out} \to v_{in})$ 容量 = 1
数字总和	经过即产生收益	内部边费用 = $-Value$ (取反求最小费)

📶 信号反射 & 思维模板

关键信号 (Key Signals)：
- “ $m$ 条路径”：流量限制为 $m$ 。
- “互不相交” vs “节点相交” vs “边相交”：这是经典的容量分级信号。
- “数字总和最大”：最大费用最大流（或负权最小费用流）。
逻辑跃迁 (Logic Jump)：

从具体的路径描述跃迁到流量的通过权限制。
- 看到“点不能重”，想到“拆点边容量 = 1”。
- 看到“边不能重”，想到“外部连接边容量 = 1”。
- 看到“均可重”，想到“所有相关边容量 = $\infty$ ”。
快速识别 (Pattern Recognition)：

以后看到 “阶梯/梯形/网格中的 $K$ 条路径，且有多种重叠约束”，本能反应就应该是 “拆点费用流 + 三级容量控制模型”。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-31 22:21:06
 * Modified for Min-Cost Max-Flow
 */

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5; // 点
const int maxe = 2e6+5; // 边 (注意：要是题目边数的2倍)
const long long INF = 1e18;
const int INF_INT = 0x3f3f3f3f;

int n,m;
int s,t; // 源点 汇点

// 坐标映射
int val[45][45];
int node_id[45][45];

// 存图的模板

//oisnip_begin code/graph/linklist.cpp 内容开始

struct linkList {
    // 修改点1: 增加 c (cost) 字段
    typedef struct {int u,v,w,c,next;} edge; 
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    // 修改点2: add 增加 cost 参数
    void add(int u,int v,int w=0, int c=0){
        e[edge_cnt] = {u,v,w,c,h[u]};
        h[u] = edge_cnt++;
    }
    
    //下标访问
    edge& operator[](int i){ return e[i]; }
} e;

//oisnip_end code/graph/linklist.cpp 内容结束


// MCMF 算法模板 - 基于linkList存图
// 最小费用最大流
struct MCMF {
    int dis[maxn];   // SPFA 最短路（最小费用）
    int flow[maxn];  // 到达当前节点的最小流量限制
    int pre[maxn];   // 记录路径：前驱节点
    int last[maxn];  // 记录路径：前驱边
    bool vis[maxn];  // SPFA 队列标记
    int n;           // 节点数
    
    long long max_flow;
    long long min_cost;

    void init(int n) {
        // 重置linkList
        e.reset();
        this->n = n;
    }
    
    // 添加边：从u到v，容量为cap，单位费用为cost
    void addEdge(int u, int v, int cap, int cost) {
        e.add(u, v, cap, cost);      // 正向边：容量cap，费用cost
        e.add(v, u, 0, -cost);       // 反向边：容量0，费用-cost
    }
    
    // SPFA 寻找单位费用最小的增广路
    // 返回是否能到达汇点
    bool spfa(int s, int t) {
        // 初始化
        for(int i = 0; i <= n+1; i++) dis[i] = INF_INT, vis[i] = 0, flow[i] = INF_INT;
        
        queue<int> q;
        dis[s] = 0;
        vis[s] = 1;
        pre[t] = -1; // 标记汇点前驱，用于判断是否可达
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            
            // 使用linkList的遍历方式
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v;
                int cap = e[i].w;
                int cost = e[i].c;

                // 如果有残余容量 且 路径费用更小
                if (cap > 0 && dis[v] > dis[u] + cost) {
                    dis[v] = dis[u] + cost;
                    pre[v] = u;    // 记录前驱节点
                    last[v] = i;   // 记录前驱边
                    flow[v] = min(flow[u], cap); // 更新路径上的最小流量限制
                    
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        
        return pre[t] != -1;
    }
    
    // 计算 最小费用 & 最大流
    // 结果保存在成员变量 max_flow 和 min_cost 中
    // 也可以修改函数返回 pair<long long, long long>
    void solve(int s, int t) {
        max_flow = 0;
        min_cost = 0;
        
        // 只要还能找到费用最小的路径（SPFA），就继续增广
        while (spfa(s, t)) {
            int now = t;
            int f = flow[t]; // 本次增广的流量
            
            max_flow += f;
            min_cost += (long long)f * dis[t];
            
            // 回溯更新残留网络
            while (now != s) {
                int edge_idx = last[now]; // 当前边的下标
                
                e[edge_idx].w -= f;       // 正向边容量减少
                e[edge_idx ^ 1].w += f;   // 反向边容量增加
                
                now = pre[now]; // 向前移动
            }
        }
    }
} mcmf;


int cnt = 0;
void init(){

    cin >> m >> n;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m+i-1; ++j) {
            cin >> val[i][j];
            node_id[i][j] = ++cnt;
        }
}

void solve_rule (int r) {
    int S = 0, T = 2 * cnt + 1;
    mcmf.init(T);
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m+i-1; ++j) {
            int in = node_id[i][j], out = in + cnt;
            // 内部边：点容量。
            // 规则1：点互不相交 -> cap=1
            // 规则2,3：点可相交 -> cap=INF
            mcmf.addEdge(in, out, (r == 1 ? 1 : INF_INT), -val[i][j]);

            if(i == 1) mcmf.addEdge(S, in, 1, 0); // 顶端起点

            // 连接汇点 T 的逻辑
            // 规则1：终点互不相交 -> cap=1
            // 规则2,3：终点可相交 -> cap=INF
            if(i == n) mcmf.addEdge(out, T, (r == 1 ? 1: INF_INT), 0); // 底端终点

            if(i < n) {
                // 外部边：边容量
                // 规则1,2：边互不相交 -> cap=1
                // 规则3：边可相交 -> cap=INF
                mcmf.addEdge(out, node_id[i+1][j], (r <= 2 ? 1 : INF_INT), 0);
                mcmf.addEdge(out, node_id[i+1][j+1], (r <= 2 ? 1 : INF_INT), 0);
            }
        }
    }
    mcmf.solve(S, T);
    cout << -mcmf.min_cost << endl;
};

// 使用示例：
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init();

    
    

    solve_rule(1);
    solve_rule(2);
    solve_rule(3);

    return 0;
}

/*
复杂度分析：
- 时间复杂度：基于SPFA的MCMF算法，复杂度为 O(k * E * F)，其中 F 是最大流，k 是常数（SPFA平均复杂度）。
- 空间复杂度：O(V + E)

使用说明：
1. 创建实例：MCMF mcmf;
2. 初始化：mcmf.init(n);
3. 添加边：mcmf.addEdge(u, v, cap, cost);
4. 求解：mcmf.solve(s, t);
5. 获取结果：mcmf.max_flow 和 mcmf.min_cost

注意事项：
- 节点编号：确保 init(n) 中的 n 覆盖了所有节点编号（建议传 max_node_index）。
- 费用类型：如果费用可能很大，注意 min_cost 使用 long long。
- 负费用：SPFA 可以处理负费用边，但图中不能有负权回路。
*/

目录