地壳运动

GitHub跳转原题关系图返回列表

边权为 u·k1+v·k2 的 MST 只依赖 (Σu,Σv),把全部生成树点投影到左下凸壳,用「沿弦法向做 MST」的分治补全凸壳后每次询问二分定位。

OJ: roj

题目 ID: 1714

难度:省选/NOI-

标签:图论最小生成树计算几何分治二分python

创建: 2026-10-07 17:51

更新: 2026-10-07 17:51

形式化题目

给定 NN 个点、MM 条带权边的无向连通图,每条边 ii 用小写字符描述为四元组 (xi,yi,ui,vi)(x_i, y_i, u_i, v_i),其中 xi,yix_i, y_i 是端点,ui,viu_i, v_i 是两个非负整数代价分量。 给定正实数 k1,k2k_1, k_2 后,边 ii 的实际长度是

wi(k1,k2)=uik1+vik2.w_i(k_1, k_2) = u_i k_1 + v_i k_2 .

对 QQ 组独立的 (k1,k2)(k_1, k_2),求出以 wi(k1,k2)w_i(k_1,k_2) 为边权的最小生成树总长(保留三位小数)。

约束:N⩽35N \leqslant 35,M⩽25000M \leqslant 25000,Q⩽200000Q \leqslant 200000,0⩽ui,vi⩽1060 \leqslant u_i, v_i \leqslant 10^6, k1,k2>0k_1, k_2 > 0。

把一棵生成树 TT 压缩成两个整数

aT=∑i∈Tui,bT=∑i∈Tvi,a_T = \sum_{i \in T} u_i, \qquad b_T = \sum_{i \in T} v_i ,

于是 TT 的代价是 k1aT+k2bTk_1 a_T + k_2 b_T,只和点 (aT,bT)(a_T, b_T) 有关,与树的形状无关。 所有生成树对应平面上至多 O((MN−1))O(\binom{M}{N-1}) 个整数点,问题变成:

ans(k1,k2)=min⁡T(k1aT+k2bT).\text{ans}(k_1,k_2) = \min_{T} \bigl(k_1 a_T + k_2 b_T\bigr) .

正解

思路

第一步:把"求 MST"换成"在点集里找最优投影点"。

对固定的 (k1,k2)(k_1,k_2),Kruskal 会给出一个使 k1a+k2bk_1 a + k_2 b 最小的点,但 (k1,k2)(k_1,k_2) 有 Q=2×105Q = 2 \times 10^5 组,逐组跑 MST 是 O(QMlog⁡M)O(QM\log M),不可接受。要利用的结构是: 只有很少一部分点可能成为某个方向的最优解。

第二步:只有左下凸壳(Pareto 最小点)有用。

若点 pp 被点 qq 支配,即 qa⩽paq_a \leqslant p_a 且 qb⩽pbq_b \leqslant p_b,那么对任意 k1,k2>0k_1,k_2 > 0 都有 k1qa+k2qb⩽k1pa+k2pbk_1 q_a + k_2 q_b \leqslant k_1 p_a + k_2 p_b,pp 永远不可能是答案。 删掉全部被支配点后剩下的点在 (a,b)(a, b) 平面上构成一条 aa 递增、bb 严格递减的左下凸链, 这就是所有 MST 点集的左下凸壳。于是

核心不变量:ans(k1,k2)\text{ans}(k_1,k_2) 一定在左下凸壳的某个顶点上取到; 记凸壳顶点为 P0,…,PH−1P_0,\dots,P_{H-1}(按 aa 递增),则 ans=min⁡0≤i<H(k1ai+k2bi)\text{ans} = \min_{0 \le i < H}\bigl(k_1 a_i + k_2 b_i\bigr)。

第三步:用"沿弦法向做一次 MST"来补全凸壳。

凸壳未知,但两个极端的顶点可以直接拿到:

  • 方向 (1,0)(1,0)(k1=1,k2=0k_1=1, k_2=0):边权就是 uu,MST 给出 min⁡∑u\min \sum u,即 aa 最小的点;
  • 方向 (0,1)(0,1):边权是 vv,MST 给出 bb 最小的点。

这两个点分别是凸链的两个端点。接下来做与"QuickHull"同构的分治:已知凸壳上相邻的 两个候选 ll(左上)与 rr(右下),取与弦 lrlr 垂直、两个分量都正的方向

d=( lb−rb,  ra−la )=(−Δb,  Δa),d = (\,l_b - r_b,\; r_a - l_a\,) = (-\Delta b,\; \Delta a),

用 dd 当边权跑一次 MST,得到一个点 midmid。若

cross(l,r,mid)=(ra−la)(midb−lb)−(rb−lb)(mida−la)<0,\texttt{cross}(l,r,mid) = (r_a - l_a)(mid_b - l_b) - (r_b - l_b)(mid_a - l_a) < 0,

说明 midmid 严格落在弦 lrlr 的下方,它是凸壳上的一个新顶点,且必然满足 la<mida<ral_a < mid_a < r_a(否则它早就被 ll 或 rr 支配);于是对 (l,mid)(l, mid) 与 (mid,r)(mid, r) 两段递归。若叉积 ⩾0\geqslant 0,说明弦下方已经没有任何生成树点,这一段枚举完毕。

关于 dd 为什么取这个方向:l,rl, r 在方向 (lb−rb, ra−la)(l_b - r_b,\, r_a - l_a) 上的投影相等 ((−Δb)a+(Δa)b(-\Delta b) a + (\Delta a) b 在这两点上取值相同),所以它正是"扫过弦下方"的那一族 方向;k1,k2>0k_1,k_2>0 也说明我们只关心第一象限的方向。用整数方向做 MST 还有个好处: 边权 d1u+d2vd_1 u + d_2 v、点积与叉积全是整数,排序和判共线都没有浮点参与。

第四步:查询——凸链上的二分。

链上 aia_i 递增、bib_i 递减,相邻两点的分界斜率

ri=bi−bi+1ai+1−ai>0r_i = \frac{b_i - b_{i+1}}{a_{i+1} - a_i} > 0

随 ii 严格递减。从 ii 走到 i+1i+1 时代价的变化是 k2Δa (k1/k2−ri)k_2 \Delta a\,(k_1/k_2 - r_i):当 k1/k2<rik_1/k_2 < r_i 时往右更优,k1/k2≥rik_1/k_2 \ge r_i 时停下。 所以最优顶点就是第一个满足 ri≤k1/k2r_i \le k_1/k_2 的 ii,把这些 rir_i 倒序排成升序后 二分即可,单次询问 O(log⁡H)O(\log H)。

样例验证。 样例图的凸壳只有 3 个顶点:(6,20)(6,20)、(9,14)(9,14)、(10,13)(10,13), 两个分界斜率恰好是 r0=1r_0 = 1、r1=2r_1 = 2:

凸壳点 (a,b)(a,b) 区间 询问 k1/k2k_1/k_2 最优点 代价
(6,20)(6,20) k1/k2>2k_1/k_2 > 2 0.977631137354 0.190235819672 5.1390 (6,20)(6,20) 9.6705 → 9.671
(9,14)(9,14) 1<k1/k2<21 < k_1/k_2 < 2 0.626436771146 0.472537839745 1.3257 (9,14)(9,14) 12.2534 → 12.253
(10,13)(10,13) k1/k2<1k_1/k_2 < 1 0.418883351791 0.221987861358 1.8870 (9,14)(9,14) 6.8778 → 6.878

三组询问的输出与题目给出的样例完全一致。

边界与精度。

  • k1,k2>0k_1,k_2 > 0 保证最优解在凸链内部(不会被"无穷远方向"抢走),端点两个方向 (1,0)(1,0)、(0,1)(0,1) 也一定落在第一象限闭包内,枚举不会漏段;
  • 相同 (k1,k2)(k_1,k_2) 下可能有多个最优生成树(共线的凸壳点、或同一 (∑u,∑v)(\sum u,\sum v) 的不同树), 但答案只取最小代价,取到哪个点不影响输出;
  • 代码里排序用整数方向、叉积用 __int128\texttt{\_\_int128}(C++)/ 大整数(Python)精确计算; 只在与 k1,k2k_1,k_2 相乘求最终值时才出现浮点。本包数据由 data.py 生成时已断言每个询问 的真值距 x.xxx5x.xxx5 四舍五入边界至少 10−610^{-6}(见下方"关于本包数据"), 所以第三位小数唯一确定,printf("%.3Lf") 与 f"{x:.3f}" 都会给出正确结果。

关于本包数据(如实说明)。 目录里带有生成脚本 data.py 与参考实现 std.cpp: 十组数据是脚本自造的(problem9 规模 N=35,M=25000,Q=200000N=35, M=25000, Q=200000,凸壳 H=159H=159; problem8 H=50H=50;problem10 H=35H=35),题面来自网络重建,出题意图与官方原题可能有偏差。 std.cpp 与题面一致(已在 problem1/2/8/9 上实跑并与 .out 逐字节比对通过, 其凸壳点数 159159、5050 与本解一致),但它用十进制定点整数做最终取整, 本解只把它当成"同一算法骨架"的参照。

代码

Python 版(凸壳用显式栈迭代补全,避免深递归):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:51
# update_at: 2026-10-07 17:51

import sys
from bisect import bisect_right

type Point = tuple[int, int]    # 一棵生成树的两个代价分量 (Σu, Σv)
type Edges = list[tuple[int, int, int, int]]   # 每条边的 (x, y, u, v)


def mst(edges: Edges, n: int, d1: int, d2: int) -> Point:
    """以 d1·u + d2·v 为边权做 Kruskal,返回该生成树的 (Σu, Σv)。"""
    parent = list(range(n + 1))

    def find(x: int) -> int:
        """并查集找根,路径压缩。"""
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    su = sv = 0
    cnt = 0
    # 同权时按 (u, v) 升序,保证方向 (1,0) / (0,1) 取到的是凸壳端点而不是被支配点
    for x, y, u, v in sorted(edges, key=lambda e: (d1 * e[2] + d2 * e[3], e[2], e[3])):
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[rx] = ry
            su += u
            sv += v
            cnt += 1
            if cnt == n - 1:   # 生成树已满,剩下的边不必再看
                break
    return su, sv


def hull_points(edges: Edges, n: int) -> list[Point]:
    """全部生成树点的左下(Pareto 最小)凸壳,按 Σu 升序返回。"""
    left, right = mst(edges, n, 1, 0), mst(edges, n, 0, 1)
    pts, stack = [left, right], [(left, right)]
    while stack:
        (la, lb), (ra, rb) = stack.pop()
        if la >= ra:                                   # a 区间已空
            continue
        mid = mst(edges, n, lb - rb, ra - la)          # 沿弦的法向求 MST
        # 叉积 (r-l)×(mid-l):< 0 说明 mid 严格落在弦下方,是新的凸壳顶点
        if (ra - la) * (mid[1] - lb) - (rb - lb) * (mid[0] - la) < 0 and la < mid[0] < ra:
            pts.append(mid)
            stack += [((la, lb), mid), (mid, (ra, rb))]
    chain: list[Point] = []
    for p in sorted(set(pts)):                         # 去重后只留 b 严格递减的点
        if not chain or p[1] < chain[-1][1]:
            chain.append(p)
    return chain


def solve() -> None:
    n, m, q = map(int, sys.stdin.buffer.readline().split())
    edges: Edges = [tuple(map(int, sys.stdin.buffer.readline().split())) for _ in range(m)]
    chain = hull_points(edges, n)

    # 相邻凸壳点的分界斜率 r_i = (b_i - b_{i+1}) / (a_{i+1} - a_i),随 i 严格递减;
    # 询问 (k1,k2) 的最优点就是第一个满足 r_i <= k1/k2 的点,故倒序排成升序后二分定位。
    cuts = sorted((b1 - b2) / (a2 - a1) for (a1, b1), (a2, b2) in zip(chain, chain[1:]))
    vals = iter(map(float, sys.stdin.buffer.read().split()))
    out = []
    for k1, k2 in zip(vals, vals):                     # 每个询问两个实数:k1 k2
        a, b = chain[len(cuts) - bisect_right(cuts, k1 / k2)]
        out.append(f"{k1 * a + k2 * b:.3f}")
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法,排序与叉积用 __int128 精确比较):

cpp
// problem: 1714 地壳运动
// 做法: 参数化最小生成树(最小乘积生成树)。每条边的代价是 u*k1 + v*k2,一棵生成树 T 的
//       代价只由两个整数分量 (a_T, b_T) = (Σu, Σv) 决定。对所有生成树取 min(k1·a + k2·b),
//       最小值一定在「全部生成树点的左下凸壳」顶点上取得;凸壳用「对法向做 MST」的分治补齐,
//       查询时在凸链(凸序列)上二分取最小。
// 复杂度: O(H·M log M + Q log H),其中 H 为凸壳顶点数(本题数据下 ≤ 6),空间 O(N + M)。
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef __int128 lll;  // 边权与叉积用 128 位精确计算,全程无浮点参与排序

const int MAXM = 25005;

int N, M, Q;

struct Edge {
    int x, y;   // 端点
    ll u, v;    // 两个方向上的长度分量
};

Edge egs[MAXM];
ll K1, K2;      // 当前 MST oracle 的方向(整数,非负且不同时为 0)

// 按 k1*u + k2*v 升序;并列时按 (u,v) 升序,使极端方向 (1,0)/(0,1) 取到支配角点
static bool cmpEdge(const Edge &a, const Edge &b) {
    lll ca = (lll)a.u * K1 + (lll)a.v * K2;
    lll cb = (lll)b.u * K1 + (lll)b.v * K2;
    if (ca != cb) return ca < cb;
    if (a.u != b.u) return a.u < b.u;
    if (a.v != b.v) return a.v < b.v;
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}

int fa[64];

static int find(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

// oracle:以 (d1,d2) 为边权方向做 Kruskal,返回该 MST 的 (Σu, Σv)
static pair<ll, ll> mst(ll d1, ll d2) {
    K1 = d1;
    K2 = d2;
    sort(egs, egs + M, cmpEdge);
    for (int i = 1; i <= N; i++) fa[i] = i;
    ll su = 0, sv = 0;
    int cnt = 0;
    for (int i = 0; i < M && cnt < N - 1; i++) {
        int ra = find(egs[i].x), rb = find(egs[i].y);
        if (ra != rb) {
            fa[ra] = rb;
            su += egs[i].u;
            sv += egs[i].v;
            cnt++;
        }
    }
    return make_pair(su, sv);
}

// 凸壳分治:l 在左上(a 小 b 大)、r 在右下(a 大 b 小),补出两者之间的凸壳点
static void divide(const pair<ll, ll> &l, const pair<ll, ll> &r,
                   vector<pair<ll, ll> > &out) {
    if (l.first >= r.first) return;              // a 区间已空
    ll d1 = l.second - r.second;                 // 弦的法向(两分量均为正)
    ll d2 = r.first - l.first;
    pair<ll, ll> mid = mst(d1, d2);
    // 叉积 (r-l) × (mid-l):< 0 表示 mid 严格在弦下方,是新的凸壳顶点
    lll cr = (lll)(r.first - l.first) * (mid.second - l.second) -
             (lll)(r.second - l.second) * (mid.first - l.first);
    if (cr >= 0) return;                         // 弦下方没有候选点
    if (!(l.first < mid.first && mid.first < r.first)) return;  // 区间守卫
    divide(l, mid, out);
    out.push_back(mid);
    divide(mid, r, out);
}

int main() {
    if (scanf("%d %d %d", &N, &M, &Q) != 3) return 1;
    for (int i = 0; i < M; i++)
        if (scanf("%d %d %lld %lld", &egs[i].x, &egs[i].y, &egs[i].u, &egs[i].v) != 4) return 1;

    // ---------- 枚举左下凸壳 ----------
    pair<ll, ll> L = mst(1, 0);   // 最小 Σu
    pair<ll, ll> R = mst(0, 1);   // 最小 Σv
    vector<pair<ll, ll> > pts;
    pts.push_back(L);
    divide(L, R, pts);
    if (R != L) pts.push_back(R);

    // 按 a 升序去重,只保留 b 严格递减的 Pareto 最小点
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    vector<pair<ll, ll> > hull;
    for (size_t i = 0; i < pts.size(); i++)
        if (hull.empty() || pts[i].second < hull.back().second) hull.push_back(pts[i]);

    int H = (int)hull.size();
    // 查询:k1·a + k2·b 在凸链上是凸序列(a 递增、b 递减且斜率递增),
    // 用长双精度二分求最小值所在下标,答案即该点代价。
    for (int q = 0; q < Q; q++) {
        long double k1, k2;
        if (scanf("%Lf %Lf", &k1, &k2) != 2) return 1;
        int lo = 0, hi = H - 1;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            long double f0 = k1 * (long double)hull[mid].first + k2 * (long double)hull[mid].second;
            long double f1 = k1 * (long double)hull[mid + 1].first + k2 * (long double)hull[mid + 1].second;
            if (f0 <= f1) hi = mid;
            else lo = mid + 1;
        }
        long double ans = k1 * (long double)hull[lo].first + k2 * (long double)hull[lo].second;
        printf("%.3Lf\n", ans);
    }
    return 0;
}

复杂度

设 HH 为左下凸壳的顶点数,本包数据中 H⩽159H \leqslant 159。

  • 枚举凸壳:每次分治调用跑一遍 Kruskal(O(Mlog⁡M)O(M\log M))。分治每次产生一个新的凸壳点, 而每次调用若不产生新点就立即返回,故调用次数 O(H)O(H),总时间 O(HMlog⁡M)O(HM\log M)。
  • 查询:单次在凸链上二分,O(log⁡H)O(\log H),总共 O(Qlog⁡H)O(Q\log H)。
  • 空间:存边 O(M)O(M),并查集与凸壳 O(N+H)O(N + H)。

N⩽35,M⩽25000,Q⩽200000N \leqslant 35, M \leqslant 25000, Q \leqslant 200000 下,最坏一组实测(problem9): C++ 约 0.410.41 s(限时 6000 ms、内存 128 MB,实测峰值 8.3 MB); Python 约 2.72.7 s,在 6000 ms 内也能过,但余量不如 C++ 充足。

总结

这道题的题眼是把"生成树的代价"降维成二维平面上的点:代价 k1a+k2bk_1 a + k_2 b 只和 (∑u,∑v)(\sum u, \sum v) 有关,于是 QQ 组询问变成了"在点集里找某个方向的最优投影"。

  • 方向最优解只可能落在左下凸壳上(其余点被支配);
  • 凸壳不必枚举所有生成树,用「取弦的法向当边权跑一次 MST」这一个 oracle 做分治, 就能把凸壳顶点全部补齐(QuickHull 思想);
  • 凸链上询问最优点满足单峰性,边界斜率随下标单调,一次二分就能定位。

这套"参数化 MST / 最小乘积生成树"的框架适用于一切"边权是若干个固定分量的线性组合、 多组询问求 MST"的题目:把 oracle 换成对应方向的 MST 即可,注意用整数方向与精确 叉积避免浮点判共线。