题目解析

一句话本质

最大费用流建模的区间选择问题，将区间选择转化为流量分配，利用节点间的容量限制实现每个点最多被覆盖k次。

• 限制每个点最多被覆盖 k 次
• 求取: 最长的可选区间的长度和

🧠 问题分析与离散化

核心矛盾

我们需要从 $n$ 个区间中选择一个子集 $S$，满足：

1. 容量约束：任意点 $x$ 最多被 $k$ 个区间覆盖
2. 优化目标：最大化所选区间的总长度 $\sum |z|$

这是一个典型的资源受限的区间调度问题，其中“资源”就是每个点的覆盖次数容量 $k$。

离散数学视角

设区间集合 $I = \{[l_i, r_i)\}$，长度 $w_i = r_i - l_i$

对于任意实数点 $x$，定义：

• 覆盖函数：$\mathrm{cov}(x) = |\{ i \in S : l_i \le x < r_i \}|$
• 约束：$\forall x \in \mathbb{R},\ \mathrm{cov}(x) \le k$
• 目标：$\max \sum w_i\cdot x_i$，其中 $x_i \in \{0,1\}$ 表示是否选择区间 $i$

这是一个0-1整数线性规划问题，但通过流网络可以高效求解。

🌉 网络流建模（核心思想）

参考了: 题解 P3358 【最长k可重区间集问题】 - 洛谷专栏

核心想表达的逻辑是：利用网络流的“串联”和“并联”物理特性来模拟区间的“相容”与“互斥”。

1. 核心逻辑：电流与电阻

文中提到了一个物理直觉：

• 串联 (Series)：代表“先后发生”。如果你选了区间 A，紧接着还能选区间 B，说明它们在时间（坐标）上没有重叠冲突。
• 并联 (Parallel)：代表“同时发生”。在同一段坐标内，如果好几个区间都要选，它们就是并联关系。
• 流量限制 (Current Limit)：总电流（流量）限制为 $K$。这意味着在电路的任何一个截面上，并联的电阻（区间）不能超过 $K$ 个。

串联容易理解并建立模型,但是并联 怎么建立模型 注意 截面 指的是: 网络流的 截面

2. 建图步骤拆解 (针对样例)

第一步：离散化 (建立“电线杆”)

首先，我们将所有区间的端点（$l$ 和 $r$）提取出来，排序并去重。这些点就是我们电路图中的接线柱（节点）。

• 原始数据：[1, 7], [6, 8], [7, 10], [9, 13]
• 端点集合：1, 7, 6, 8, 7, 10, 9, 13
• 排序去重后节点：1, 6, 7, 8, 9, 10, 13

这些点构成了我们的主干道。

第二步：铺设主干电缆 (Main Wire)

图片中提到的“不相交就由 $r$ 连向 $l$”，在图论实现中，就是连接相邻的离散点。

• 连边逻辑：从点 $i$ 连向点 $i+1$。
• 容量 (Cap)：$K$ (样例中为 2)。这代表“如果不选区间，这里最大可以通过 2 的空闲流量”。
• 费用 (Cost)：0。走主干道没有收益。

第三步：接入区间电阻 (Interval Arcs)

每一个区间，相当于一根跨接在两个接线柱之间的“有收益导线”。

• 连边逻辑：对于区间 $[u, v]$，从节点 $u$ 连向节点 $v$。
• 容量 (Cap)：1。每个区间只能选一次。
• 费用 (Cost)：$-Length$ (即 $-(v-u)$)。因为要求最大长度，我们取负求最小费用。

第四步：接入电源 (Source/Sink)

• 超级源点 S：连向第一个点 (1)，容量 $K$，费用 0。
• 超级汇点 T：从最后一个点 (13) 连入，容量 $K$，费用 0。

3. Mermaid 可视化详解

这就是基于图片逻辑生成的样例图。请仔细观察红色虚线（区间）是如何“分流”黑色实线（主干）的流量的。

graph LR
    %% 定义节点样式
    classDef mainNode fill:#fff,stroke:#333,stroke-width:2px;
    classDef sourceSink fill:#f96,stroke:#333,stroke-width:2px,color:white;
  
    S((S)):::sourceSink
    T((T)):::sourceSink
  
    N1((1)):::mainNode
    N6((6)):::mainNode
    N7((7)):::mainNode
    N8((8)):::mainNode
    N9((9)):::mainNode
    N10((10)):::mainNode
    N13((13)):::mainNode

    %% 1. 主干道 (黑色实线)
    %% 代表空闲资源流转，容量为 K=2
    S ==>|Cap:2, Cost:0| N1
    N1 ==>|Cap:2, Cost:0| N6
    N6 ==>|Cap:2, Cost:0| N7
    N7 ==>|Cap:2, Cost:0| N8
    N8 ==>|Cap:2, Cost:0| N9
    N9 ==>|Cap:2, Cost:0| N10
    N10 ==>|Cap:2, Cost:0| N13
    N13 ==>|Cap:2, Cost:0| T

    %% 2. 区间边 (红色虚线)
    %% 代表选择区间，容量为 1，Cost 为负长度
    %% 区间1: [1, 7], len 6
    N1 -.->|Cap:1, Cost:-6| N7
  
    %% 区间2: [6, 8], len 2
    N6 -.->|Cap:1, Cost:-2| N8
  
    %% 区间3: [7, 10], len 3
    N7 -.->|Cap:1, Cost:-3| N10
  
    %% 区间4: [9, 13], len 4
    N9 -.->|Cap:1, Cost:-4| N13

    linkStyle 0,1,2,3,4,5,6,7 stroke-width:3px,fill:none,stroke:black;
    linkStyle 8,9,10,11 stroke-width:3px,fill:none,stroke:red,stroke-dasharray: 5 5;

注意这个图上的并联的实现

4. 深度解析：为什么这张图是对的？

让我们回到图片作者提到的“串联”与“并联”：

场景一：区间 1 [1, 7] 和 区间 3 [7, 10]

• 流向：流量从 $S$ 出来，可以先走红色虚线 1->7 (选了区间1)，到达点 7 后，立刻接着走红色虚线 7->10 (选了区间3)。
• 物理连接：这就是串联。
• 意义：因为首尾相接，同一个单位的流量（1 unit flow）可以连续吃掉这两个区间。这反映了它们不冲突，只需要占用 1 个通道配额。

场景二：区间 2 [6, 8] 和 区间 3 [7, 10]

• 流向：
  • 流 A 走了 6->8 (区间2)。
  • 流 B 走了 7->10 (区间3)。
• 冲突点：在截面 7->8 这段主干道上，流 A 正在 6->8 的“高架桥”上飞越，流 B 刚刚从点 7 起飞进入 7->10 的高架桥。
• 物理连接：这就是并联。
• 意义：它们在空间上重叠了。为了同时维持这两个流，我们必须消耗 2 个单位 的总流量（即 $K$ 必须 $\ge 2$）。如果 $K=1$，流量不够分，就只能二选一。

5. 教练总结

图片中作者强调的思路，翻译成工程语言就是：

1. 时间轴是河床（节点和主干边）。
2. K 是河水的总流量。
3. 区间是运河（支流）。
4. 如果你开凿一条运河 u->v，水流就会从主河道分流进运河。
5. 费用流算法会自动帮我们分配水流，使得流经“运河”（即选择区间）的总长度最大。

这个建模方式是解决 “K重覆盖问题” 的标准指纹。你看懂这张图的流动逻辑了吗？

具体构图

1. 离散化所有端点：将所有区间的左右端点收集、排序、去重，得到m个关键点
2. 构建链式结构：
   • 创建节点：源点s，汇点t，每个离散化点对应一个节点
   • 对于相邻点i→i+1：添加容量为k，费用为0的边
3. 添加区间选择边：
   • 对于每个区间[l, r)，找到对应离散化节点u(左)和v(右)
   • 添加边u→v，容量为1，费用为 -长度（最小费用流）或 +长度（最大费用流）
4. 连接源汇：
   • s→第一个节点：容量k，费用0
   • 最后一个节点→t：容量k，费用0

为什么这样建模？

• 链式边：控制每个"段"的流量不超过k，对应每个点的覆盖限制
• 区间边：流量1表示选择该区间，费用为区间长度的负值（最小费用流）
• 总流量：每条从s到t的路径对应一个区间的选择，流量在链上传递

证明

上面的方法是如何保证 : 点$x$ 最多被覆盖 K 次的

这是一个非常核心的数学证明题。如果不理解这一点，做网络流题就像是在“撞大运”。

这个证明利用了网络流中最基本的定理：最大流最小割定理（Max-flow Min-cut Theorem） 的一个推论，以及 流量守恒（Flow Conservation） 定律。

我们将通过 “截面法” (The Cut Method) 来证明。

1. 建立模型：把数轴切一刀

想象我们在图上的任意两个离散点 $v_i$ 和 $v_{i+1}$ 之间，用一把刀垂直切下去。 这个切口对应实数轴上的一个小区间 $(v_i, v_{i+1})$。假设这里有一个点 $x$。

我们来看这个截面上会有哪些流量经过？

graph LR
    subgraph 左侧集合 L
    N1((...))
    Vi((Vi))
    end
  
    subgraph 右侧集合 R
    Vnext((Vi+1))
    Nlast((...))
    end

    %% 主干道流量
    Vi == "主干道流量 (f_main)" ==> Vnext

    %% 飞越的区间流量
    N1 -. "区间 A (覆盖 x)" .-> Vnext
    N1 -. "区间 B (覆盖 x)" .-> Nlast
    Vi -. "区间 C (覆盖 x)" .-> Nlast

    %% 垂直切割线
    linkStyle 0 stroke-width:4px;
  
    style Vi fill:#ddd
    style Vnext fill:#ddd

2. 数学符号定义

1. $F_{total}$ (总流量)： 整个网络从源点 $S$ 流出的总流量。 由建图可知，源点 $S \to \text{第一个点}$ 的容量限制为 $K$。

   $$F_{total} \le K \quad \text{......(公式 1)}$$

2. 截面流量 (Flow across the cut)： 根据网络流的流量守恒定律：在一个封闭系统中，任意一个将 $S$ 和 $T$ 分开的截面，其流过的净流量必须等于总流量 $F_{total}$。

   这个就是核心

3. 截面上的两种边： 在这个截面 $(v_i, v_{i+1})$ 上，流量只能通过两种方式流过：

   • 方式 A：主干道边 $(v_i \to v_{i+1})$。设其流量为 $f_{main}$。
   • 方式 B：跨越这个截面的区间边。即所有起点 $l \le v_i$ 且终点 $r \ge v_{i+1}$ 的区间边。设这些区间的集合为 $S_x$（即覆盖点 $x$ 的区间集合）。每个区间流量为 1。

3. 证明过程

步骤 1：列出守恒方程 在任意截面 $(v_i, v_{i+1})$ 处，流过的总流量等于各部分流量之和：

步骤 2：代入数值 因为每个被选中的区间流量恒为 1（容量限制）：

步骤 3：利用不等式推导 我们有两个关键的物理限制：

1. 总流量限制：$F_{total} \le K$ （源点瓶颈）。
2. 流量非负性：$f_{main} \ge 0$ （主干道流量不可能倒流，且最小为0）。

将它们代入方程：

由于 $F_{total} \le K$ 且 $f_{main} \ge 0$，我们可以得出：

证毕 (Q.E.D.)

4. 物理直觉解释（通俗版）

把这个系统想象成一条宽为 $K$ 米的大河。

• $S \to T$ 的总水量最多只有 $K$ 吨/秒。
• 主干道 是原本的河床。
• 每一个区间 是一条架设在空中的“引水管”，它从上游抽水，绕过一段距离，在下游把水排回去。

结论： 如果在某一点 $x$ 上方有 $M$ 条引水管同时在运水（即覆盖次数为 $M$），那么这 $M$ 吨水加上河床里剩下的水，总和不能超过源头的 $K$ 吨。

如果 $M > K$，那就意味着这 $M$ 条管子里的水比源头出来的总水流还多，这违背了物理定律（流量守恒）。

所以，只要源头卡死了流量是 $K$，系统中任何一个截面上并行的“引水管”数量就绝不可能超过 $K$。

5. 举个反例帮助理解

假设 $K=2$，我们在某处选了 3 个重叠的区间。

• 那么在这个截面上，需要 3 个单位的流量从这 3 条“区间边”流过去。
• 此时主干道流量 $f_{main} \ge 0$。
• 截面总流量 $= 3 + f_{main} \ge 3$。
• 但是源点总共只发出了 2 个单位的流。$2 \ge 3$ 显然矛盾。
• 因此，最大流算法自动不会选择这 3 个区间同时存在，它会放弃其中费用（长度）最小的那个，来满足 $K=2$ 的限制。

⚙️ 离散数学模块

算子映射

思维模板

资源受限区间调度 → 时间线离散化 → 构建容量链 → 添加带权区间边 → 费用流求解

快速识别

看到以下特征组合，立即想到费用流建模：

1. 特征A：区间选择问题（每个区间有收益）
2. 特征B：每个点有覆盖次数限制（容量约束）
3. 特征C：需要最大化总收益

数学推导

设离散化后得到 $m$ 个点，形成 $m-1$ 个连续段。

对于每个段 $[j, j+1)$，令其长度为 $d_j = \mathrm{pos}_{j+1} - \mathrm{pos}_j$

设 $y_j$ 表示通过段 $j$ 的流量（即覆盖该段的区间数量），则有：

• $0 \le y_j \le k$（容量约束）
• 对于区间 $i$ 覆盖段集合 $T_i$，选择区间 $i$ 则 $y_j$ 增加 1（流量守恒）

费用流模型恰好等价于：

📶 信号反射 & 思维模板

关键信号 (Key Signals)

1. “开区间集合” → 边界处理要小心
2. “任意一点x包含x的开区间个数不超过k” → 点覆盖容量约束
3. “$\sum |z|$ 达到最大” → 最大化权重和
4. 数据范围：$k \le 3,\ n \le 500$ → 费用流可行

逻辑跃迁 (Logic Jump)

从"每个点覆盖次数限制"跳跃到"流量在时间轴上的分配问题"：

• 每个点如同一个检查站，只能通过k个区间
• 区间如同车辆，从起点到终点，占用沿途所有检查站的容量
• 问题转化为：如何安排车辆路线使得总行驶距离最大

模式识别 (Pattern Recognition)

特征A（区间选择）+ 特征B（点覆盖限制）+ 特征C（最大化权重） = 费用流建模（离散化时间轴+链式容量边）

教练提示：这道题是网络流经典应用，掌握后可以解决一系列类似的资源分配问题。下次遇到"每个时间点有容量限制的活动安排"问题时，记得这个模板！

代码

/**
 * 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-02-02 12:02:22
 * 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 k;
int s,t; // 源点 汇点

// 存图的模板

//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;

void init(){
    std::cin >> n;
    std::cin >> k;
    

    mcmf.init(n); // 注意这里可能需要根据节点编号调整大小，例如 n+2
    
    for (int i = 0; i < m; i++) {
        int u, v, cap, cost;
        // 费用流通常输入4个参数：u, v, 容量, 费用
        cin >> u >> v >> cap >> cost;
        
        mcmf.addEdge(u, v, cap, cost); 
    }
}

// 使用示例：
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    
    mcmf.solve(s, t);
    
    cout << mcmf.max_flow << " " << mcmf.min_cost << "\n";
    
    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 可以处理负费用边，但图中不能有负权回路。
*/