题解：P11307 [COTS 2016] 建造费 Pristojba

jinmingyi · 2026-08-04 11:08:17 · 题解

P11307 [COTS 2016] 建造费 Pristojba

Kruskal

看到题目要求最小生成树，我第一反应是 Kruskal 算法。

观察题目，不就是把所有边建出来，再排序，然后并查集维护即可吗？

于是我兴高采烈地敲出了下面这份代码。 ::::info[点击查看 Kruskal 代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
vector<int> p;
vector<int> fa;
struct info{
    int x, l, r;
};
struct node{
    int now, u, v;
};
struct cmp{
    bool operator () (const node &a, const node &b){
        return a.now > b.now;
    }
};
int find(int now){
    if(fa[now] == now)return now;
    return fa[now] = find(fa[now]);
}
void unionset(int x, int y){
    if(find(x) == find(y))return ;
    fa[find(x)] = find(y);
}
signed main(){
    scanf("%lld%lld", &n, &m);
    p.resize(n+1);
    for(int i = 1;i <= n;i++){
        scanf("%lld", &p[i]);
    }
    fa.resize(n+1, 0);
    for(int i = 1;i <= n;i++)fa[i] = i;
    vector<info> g(m+1);
    priority_queue<node, vector<node>, cmp> q;
    for(int i = 1;i <= m;i++){
        scanf("%lld%lld%lld", &g[i].x, &g[i].l, &g[i].r);
        for(int j = g[i].l;j <= g[i].r;j++){
            q.push({p[g[i].x]+p[j], g[i].x, j});
        }
    }
    int ans = 0;
    while(!q.empty()){
        node f = q.top();
        q.pop();
        int x = f.u, y = f.v, cnt = f.now;
        if(find(x) != find(y)){
            ans += cnt;
            unionset(x, y);
        }
    }
    printf("%lld", ans);
    return 0;
}

::::

MLE。

我重新看了一下自己的代码以及题目。

发现对于每一个三元组，它最多对应了 n-1 条边，而最多有 10^5 个三元组。

图中最多可以有 10^5\times(10^5-1)\approx10^{10} 条边。

因此最坏情况下，我们要存储 10^{10} 条边。

不管是存入优先队列，还是放进数组排序，都远远超出了内存限制。

所以 Kruskal 最大的问题不是其他问题，而是要存的边数太多了。

Prim

既然存储所有的边不可行，那么有没有不用存储所有边的方法呢？

有，这时候我们就能想到 Prim 算法。

大致的过程就是每次去找当前生成树最小的出边并加入，这样就能得到最小生成树啦。

这个 Prim 算法又给了我一个新的思路：最小生成树其实可以不需要维护所有边，可以只维护最小出边。

既然如此，有没有算法能把这种思想推广到多个连通块？

答案就是 Borůvka 算法。

Borůvka

在我看来，Borůvka 算法可以理解为对 Prim 思想的一种推广。

原来的 Prim 算法是一直只有一个连通块，然后往这个连通块里面加新的最小出边。

而 Borůvka 则是同时有多个连通块，要同时找每个连通块的最小出边并合并该边连接的两个连通块。

把每个连通块看成一个点，如果这个图当前还能继续连通且每个尚未完成的连通块存在合法出边，每个连通块都至少连出一条边。合并这些边后，每个新连通块至少包含两个旧连通块，因此连通块数量至少减半，因此整个算法最多只要 O(\log n) 轮合并。

合并的问题我们解决了，现在又出现了一个新的问题：我们要怎么快速的寻找每个连通块对应的最小出边呢？

寻找最小出边

很容易想到的是暴力循环找最小出边，但是这时我们再去看一下数据范围。

每一个三元组对应的区间最长的长度是 n-1，相当于每个三元组最多会对应有 10^5 条边。

也就是说，最坏情况下一轮合并时的查找会进行约 10^10 次判断，现在这个时间复杂度已经让人不能忍受了，更别说加上 Borůvka 算法需要的 O(\log n) 轮合并了。

有没有更快的方法呢？

当然有。

注意到对于从 i 到 j 的一条边，该边的边权为 p_i+p_j 。

而对于第 i 个三元组 (x_i,l_i,r_i)，其中一个端点 x_i 已经确定。

如果要找对于这个三元组边权最小的那一条边，只用找从 l_i 到 r_i 最小的 p 就行了。

于是就能想到这里要用到线段树。

::::info[如果你没有学过线段树]

你可以先看看这几题：

• [ ] P4086，线段树维护的东西是最值

• [ ] P3353，线段树维护的是区间和，可以当做练习

::::

我们可以用线段树来维护一段区间里的最小值。

但是，问题又来了，只存一个最小值足够吗？

如果查询出来的最小值与当前点属于同一个连通块，那么这条边就不能作为最小出边。

但是，我们也可以继续在线段树中向下查找，如果当前区间维护的最小值与 x_i 属于同一个连通块，就继续向下查找；如果不是，那么就返回该答案。

如果整个区间和 x_i 属于同一个连通块，那么就返回一个极大的值。

现在看着是没有任何问题，只是，这样可行吗？

假设最坏情况下，一个区间中的所有点几乎都属于同一个连通块。

那么每次查询都可能一直遍历到线段树的叶子结点，才能找到第一个合法答案。

这样一次查询最坏会退化成 O(n)。

而每轮 Borůvka 需要处理所有三元组，因此时间复杂度又回到了 O(nm)。

这和暴力没有太大区别。

所以，我们必须在线段树中直接维护多个答案，而不是查询失败后再继续向下寻找。

与其查询失败后再继续向下寻找，不如直接在线段树中维护多个候选答案。

肯定不能维护所有值，不然还是和暴力没有什么区别。

我们可以维护一个次小值。

光维护一个严格意义上的次小值足够吗？

我们来举个例子。

例如，一个区间中点权从小到大分别为 1,2,3,4。

其中前两个点属于同一个连通块 A，第三个点属于连通块 B，第四个点属于连通块 C。

如果当前查询的点也属于连通块 A，那么区间中的最小值和严格意义上的次小值都属于连通块 A，仍然不能作为最小出边。

为了找到真正合法的答案，我们还是需要继续向下查找。

这时候就和原来没有加次小值一样了。

我们能不能重新定义一下次小值呢？

当然可以。

这里的次小值并不是严格意义上的第二小，而是与当前区间最小值不属于同一个连通块的最小值。

线段树维护最小值和次小值

现在，我们已经知道我们要用线段树来维护最小值和与最小值不属于同一个连通块的最小值（后面简称次小值）。

因此，对于线段树的每个区间，我维护了两组信息：

第一组（后缀为 1）表示当前区间的最小值以及其相关的变量，第二组（后缀为 2）表示当前区间的次小值以及其相关的变量。

对于每一组信息，维护的三个变量分别是：

定义好之后我们就碰到了第一个问题，当区间的长度为 1 的时候，要怎么维护次小值呢？

很简单，只用把次小值赋值成一个极大的值，并将 xb 和 ltk 赋值为 -1 即可。

然后我们又碰到了第二个问题，怎么从父节点继承子节点的状态呢？

现在父节点的状态只能从以下四个状态中得到：

1. 左节点的最小值；
2. 左节点的次小值；
3. 右节点的最小值；
4. 右节点的次小值。

为什么只需要这四个值？

因为左右儿子都已经维护好了自己的最优答案。

对于任意一个儿子而言，除了最小值之外，其余所有合法答案都不会优于自己的次小值。

所以，父节点只需要从这四个候选中选择即可。

首先将这四个候选按照点权从小到大排序。

最小的就是父节点的最小值。

继续向后扫描，第一个与最小值不属于同一个连通块的，就是父节点的次小值。

如果次小值不存在，则将次小值赋值为一个极大值，并将 xb 和 ltk 赋值为 -1 即可。

一轮 Borůvka 中如何寻找最优的出边

对于每个三元组 (x_i,l_i,r_i)，先在线段树上查询区间 [l_i,r_i]。

该图的边是无向边，所以不仅要存储从 x_i 出发的边，还要记录一个反向的边。

如果区间最小值与 x_i 不属于同一个连通块，就返回最小值；否则返回次小值。

这样得到的点，就是当前三元组中从 x_i 出发能够连接到的最优合法点。

对应代码：

for(int i = 1;i <= m;i++){
        int x = g[i].x;
        ylpx ext = ans(1, n, g[i].l, g[i].r, 1, x);
        if(ext.xb == -1){
            continue;
        }
        if(!mmap.count(find(x)) || mmap[find(x)].second > p[x]+p[ext.xb]){
        mmap[find(x)] = {find(ext.xb), p[x]+p[ext.xb]};
    }
}

其中，mmap[now] 记录的是连通块 now 对应的最优出边。