Interval - 题解

标签与难度

标签: 图论, 最短路, Dijkstra, 最小割, 对偶图, 网格图难度: 2100

题目大意喵~

好久不见呀，指挥官！今天我们来玩一个关于区间变化的游戏，喵~

我们一开始有一个区间 [1, n]。对于任何一个区间 [l, r]，只要 l < r，它就可以发生两种变化：

收缩: 变成 [l+1, r] 或者 [l, r-1]。
扩张: 变成 [l-1, r] (要求 l > 1) 或者 [l, r+1] (要求 r < n)。

当一个区间变成 l = r 的形式时，它就再也不能变化了，就像一只懒洋洋睡着了的猫咪，不动啦。但我们不喜欢这样！我们想让这个区间永远“活”下去，永远不要变成 l = r 的样子。

为了达到这个目的，我们可以花一些代价来“禁止”某些变化。一个禁令形如 (l, r, dir, c)：

如果 dir = 'L'，我们可以花 c 的代价，双向禁止 [l, r] 和 [l+1, r] 之间的转换。
如果 dir = 'R'，我们可以花 c 的代价，双向禁止 [l, r] 和 [l, r-1] 之间的转换。

我们的任务就是，计算为了保证区间永远不会变成 l = r 的状态，所需要花费的最小总代价是多少。如果无论如何都无法阻止，就输出 "-1"，喵~

解题思路分析

这道题看起来是在问怎么选择禁令，其实背后藏着一个非常经典的图论模型哦，喵！让我来给你抽丝剥茧，把问题看个通透！

从“禁止”到“切割”

首先，我们把所有可能的区间 [l, r] 看作图上的一个个节点。如果两个区间可以通过一次操作（收缩或扩张）相互转换，我们就在它们对应的节点之间连一条边。这样，整个问题就变成了一个巨大的图。

我们的初始状态是节点 [1, n]。不希望看到的状态是所有形如 [i, i] 的节点。我们想让 [1, n] 永远无法到达任何一个 [i, i] 节点。

而我们能做的，就是花代价“禁止”某些转换，这不就等于花代价“切断”图上的某些边吗？我们要用最小的总代价，切断所有从 [1, n] 到达 [i, i] 集合的路径。

这...这不就是最小割问题嘛！我们想找到一个边集，切断后使得源点（[1, n]）和汇点（所有 [i, i] 组成的集合）不再连通，并且这个边集的总权值（代价）最小。

最小割与最短路的奇妙变身

虽然我们找到了最小割模型，但直接在原图上跑最大流（根据最大流最小割定理）可能会非常复杂和缓慢，因为节点数量是 $O(n^2)$ 级别的。但是，对于这种网格状的图，最小割问题有一个非常漂亮的对偶问题——最短路问题！

想象一下，把所有区间 [l, r] 放在一个二维平面上，l 是横坐标，r 是纵坐标。所有满足 1 <= l <= r <= n 的点构成了一个三角形区域。

初始状态 [1, n] 在左上角。
不希望到达的终止状态 [i, i] 构成了这个三角形的对角线。

我们所谓的“切断路径”，就像是在这个网格上修建一道“隔离墙”，把 [1, n] 和对角线 l=r 隔开。我们付出的代价就是修建这道墙的花费。而求最小代价，就是求最短的“墙”路径！

这就是对偶图的思想。我们来构建一个新图（对偶图），在这个新图上跑最短路，就能得到原图的最小割。

构建对偶图

对偶图的节点: 原图中，边围成了“面”。对偶图的节点，就对应原图的“面”或者说，原始网格的“顶点”。让我们在 l-r 平面上建立一个 (n+1) x (n+1) 的网格。对偶图的节点就是这些网格点 P(i, j)，其中 i 对应 l 轴，j 对应 r 轴。我们可以让 i 从 1 到 n+1，j 从 0 到 n。一个对偶图节点 P(l, r) 可以理解为它位于四个区间 [l-1, r], [l, r], [l-1, r-1], [l, r-1] 的交汇处。
对偶图的边: 原图中的一条边（一次转换），对应对偶图中的一条边（一段“墙”）。
- 一个 (l, r, 'R', c) 的禁令，是禁止 [l, r] 和 [l, r-1] 的转换。这相当于在它们之间修一堵水平的墙。这堵墙连接了对偶图的两个相邻节点 P(l, r-1) 和 P(l+1, r-1)。所以我们在这两个节点间连一条权值为 c 的边。
- 一个 (l, r, 'L', c) 的禁令，是禁止 [l, r] 和 [l+1, r] 的转换。这相当于在它们之间修一堵垂直的墙。这堵墙连接了对偶图的两个相邻节点 P(l+1, r-1) 和 P(l+1, r)。所以我们在这两个节点间连一条权值为 c 的边。
源点 S 和汇点 T:
- 我们的“墙”需要从哪里开始，到哪里结束呢？墙需要把 [1, n] 和 l=r 对角线分开。
- [1, n] 位于整个区间的“外部边界”（即 l=1 和 r=n 构成的边界）。所以，我们可以把所有代表外部边界的对偶节点（P(1, j) 和 P(i, n)）看作墙的起点，将它们连接到一个超级源点 S，边权为0。
- l=r 对角线是我们的“内部禁区”。所以，我们可以把所有代表这条对角线的对偶节点（P(i, i-1)）看作墙的终点，将它们连接到一个超级汇点 T，边权也为0。

现在，问题就彻底转化成了：求这个对偶图中，从 S到 T 的最短路径！这就可以用经典的 Dijkstra 算法来解决啦，喵~

总结一下我们的最终策略：

建立一个对偶图，节点是 P(l, r)，其中 1 <= l <= n+1, 0 <= r <= n。
添加一个超级源点 S 和一个超级汇点 T。
根据输入的 m 个禁令，在对偶图上添加对应的边和代价。
将 S 与所有代表“外部边界”的节点相连（P(1, j) 和 P(i, n)），权值为0。
将所有代表“对角线边界”的节点（P(i, i-1)）与 T 相连，权值为0。
用 Dijkstra 算法计算从 S 到 T 的最短路。如果最短路是无穷大，说明无法修建完整的“墙”，即无法阻止，输出-1。否则，输出最短路径的长度。

是不是感觉豁然开朗了呢？把复杂的问题一步步转换成我们熟悉的模型，这就是算法的魅力所在呀，指挥官！

代码实现

下面是我为你精心准备的实现代码，注释里有详细的解释哦，喵~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <string>

// 使用 long long 来存储距离，防止溢出
using ll = long long;

// 无穷大的表示，要足够大
const ll INF = 1e18;

// 优先队列中存储的元素，包含距离和节点ID
struct State {
    ll cost;
    int u;

    // 自定义比较函数，让优先队列变成小顶堆
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

// 图中边的结构
struct Edge {
    int to;
    ll weight;
};

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    // 对偶图的维度是 (n+2) x (n+2)，为了方便处理边界，l 从 1 到 n+1, r 从 0 到 n
    // 我们用 (l, r) 来表示对偶图的节点
    // 节点总数 (n+2)*(n+1)
    int num_dual_nodes = (n + 2) * (n + 2);
    int source = num_dual_nodes;
    int sink = num_dual_nodes + 1;

    // 邻接表来存图
    std::vector<std::vector<Edge>> adj(num_dual_nodes + 2);

    // 将二维坐标 (l, r) 映射到一维的节点ID
    auto get_node_id = [&](int l, int r) {
        // l: 1..n+1, r: 0..n
        return (l - 1) * (n + 1) + r;
    };

    // 添加双向边
    auto add_edge = [&](int u, int v, ll w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };

    // 读取 m 个禁令，构建对偶图的边
    for (int k = 0; k < m; ++k) {
        int l, r;
        char dir_char;
        ll c;
        std::cin >> l >> r >> dir_char >> c;

        if (dir_char == 'R') {
            // 禁止 [l, r] <-> [l, r-1]
            // 对应对偶图中 P(l, r-1) 和 P(l+1, r-1) 之间的边
            int u = get_node_id(l, r - 1);
            int v = get_node_id(l + 1, r - 1);
            add_edge(u, v, c);
        } else { // dir_char == 'L'
            // 禁止 [l, r] <-> [l+1, r]
            // 对应对偶图中 P(l+1, r-1) 和 P(l+1, r) 之间的边
            int u = get_node_id(l + 1, r - 1);
            int v = get_node_id(l + 1, r);
            add_edge(u, v, c);
        }
    }

    // 连接超级源点 S 到外部边界
    // l=1 的边界
    for (int r = 0; r <= n; ++r) {
        add_edge(source, get_node_id(1, r), 0);
    }
    // r=n 的边界
    for (int l = 2; l <= n + 1; ++l) { // l=1 已经连过了
        add_edge(source, get_node_id(l, n), 0);
    }

    // 连接对角线边界到超级汇点 T
    // r = l-1 的边界
    for (int i = 1; i <= n + 1; ++i) {
        add_edge(get_node_id(i, i - 1), sink, 0);
    }

    // Dijkstra 算法求最短路
    std::vector<ll> dist(num_dual_nodes + 2, INF);
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        int u = current.u;
        ll cost = current.cost;

        // 如果已经有更短的路径，就跳过
        if (cost > dist[u]) {
            continue;
        }
        
        // 如果到达汇点，可以提前结束（Dijkstra特性）
        if (u == sink) {
            break;
        }

        // 遍历所有邻居
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            ll weight = edge.weight;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果
    if (dist[sink] >= INF) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << dist[sink] << std::endl;
    }

    return 0;
}

复杂度分析

时间复杂度: $O(M \log N^2)$ 或 $O(M \log (N^2))$ 。我们的图有 $V = O(N^2)$ 个节点和 $E = O(M + N)$ 条边（ $M$ 是输入的禁令数， $N$ 是连接S和T的0权边）。Dijkstra算法使用优先队列的复杂度是 $O(E \log V)$ 。所以总时间复杂度是 $O((M+N) \log(N^2)) = O((M+N) \log N)$ 。考虑到 $M$ 可能很大，写作 $O(M \log N)$ 更为贴切。这对于 $N=500, M=200000$ 的数据规模是完全可以通过的，喵~
空间复杂度: $O(N^2 + M)$ 。我们需要 $O(N^2)$ 的空间来存储邻接表和距离数组 dist。邻接表中总共存储 $O(M+N)$ 条边。所以总空间复杂度为 $O(N^2 + M)$ 。

知识点总结

这道题是一个非常棒的练习，融合了多个重要的图论知识点，喵~

问题建模: 能够识别出问题的本质是图的连通性与分割问题，是解题的第一步。将“禁止操作”抽象为“切割边”，是通往正确道路的关键。
最小割: 理解最小割问题的定义——以最小代价使得源点和汇点不连通。
对偶图: 这是本题的核心技巧！对于平面图（特别是网格图），最小割问题可以转化为其对偶图上的最短路问题。这是一个非常强大且优美的工具，能将复杂的网络流问题简化为我们更熟悉的最短路问题。
Dijkstra算法: 解决单源非负权最短路问题的标准算法。熟练掌握其原理和优先队列实现是必不可少的技能。

通过这道题，希望指挥官能更深刻地理解最小割和最短路之间的对偶关系，以后遇到类似的网格分割问题，就能立刻想到这个绝妙的思路啦！加油，喵~

Interval - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

从“禁止”到“切割” ​

最小割与最短路的奇妙变身 ​

构建对偶图 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​