边权为 u·k1+v·k2 的 MST 只依赖 (Σu,Σv),把全部生成树点投影到左下凸壳,用「沿弦法向做 MST」的分治补全凸壳后每次询问二分定位。
OJ: roj
题目 ID: 1714
难度:省选/NOI-
标签:图论最小生成树计算几何分治二分python
创建: 2026-10-07 17:51
更新: 2026-10-07 17:51
形式化题目
给定
对
约束:
把一棵生成树
于是
正解
思路
第一步:把"求 MST"换成"在点集里找最优投影点"。
对固定的
第二步:只有左下凸壳(Pareto 最小点)有用。
若点
核心不变量:
一定在左下凸壳的某个顶点上取到; 记凸壳顶点为 (按 递增),则 。
第三步:用"沿弦法向做一次 MST"来补全凸壳。
凸壳未知,但两个极端的顶点可以直接拿到:
- 方向
( ):边权就是 ,MST 给出 ,即 最小的点; - 方向
:边权是 ,MST 给出 最小的点。
这两个点分别是凸链的两个端点。接下来做与"QuickHull"同构的分治:已知凸壳上相邻的
两个候选
用
说明
关于
第四步:查询——凸链上的二分。
链上
随
样例验证。 样例图的凸壳只有 3 个顶点:
| 凸壳点 |
区间 | 询问 | 最优点 | 代价 | |
|---|---|---|---|---|---|
0.977631137354 0.190235819672 |
5.1390 | 9.6705 → 9.671 |
|||
0.626436771146 0.472537839745 |
1.3257 | 12.2534 → 12.253 |
|||
0.418883351791 0.221987861358 |
1.8870 | 6.8778 → 6.878 |
三组询问的输出与题目给出的样例完全一致。
边界与精度。
保证最优解在凸链内部(不会被"无穷远方向"抢走),端点两个方向 、 也一定落在第一象限闭包内,枚举不会漏段; - 相同
下可能有多个最优生成树(共线的凸壳点、或同一 的不同树), 但答案只取最小代价,取到哪个点不影响输出; - 代码里排序用整数方向、叉积用
(C++)/ 大整数(Python)精确计算; 只在与 相乘求最终值时才出现浮点。本包数据由 data.py生成时已断言每个询问 的真值距四舍五入边界至少 (见下方"关于本包数据"), 所以第三位小数唯一确定, printf("%.3Lf")与f"{x:.3f}"都会给出正确结果。
关于本包数据(如实说明)。 目录里带有生成脚本 data.py 与参考实现 std.cpp:
十组数据是脚本自造的(problem9 规模 problem8 problem10 std.cpp 与题面一致(已在 problem1/2/8/9 上实跑并与 .out 逐字节比对通过,
其凸壳点数
代码
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 精确比较):
// 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;
}复杂度
设
- 枚举凸壳:每次分治调用跑一遍 Kruskal(
)。分治每次产生一个新的凸壳点, 而每次调用若不产生新点就立即返回,故调用次数 ,总时间 。 - 查询:单次在凸链上二分,
,总共 。 - 空间:存边
,并查集与凸壳 。
problem9):
C++ 约
总结
这道题的题眼是把"生成树的代价"降维成二维平面上的点:代价
- 方向最优解只可能落在左下凸壳上(其余点被支配);
- 凸壳不必枚举所有生成树,用「取弦的法向当边权跑一次 MST」这一个 oracle 做分治, 就能把凸壳顶点全部补齐(QuickHull 思想);
- 凸链上询问最优点满足单峰性,边界斜率随下标单调,一次二分就能定位。
这套"参数化 MST / 最小乘积生成树"的框架适用于一切"边权是若干个固定分量的线性组合、 多组询问求 MST"的题目:把 oracle 换成对应方向的 MST 即可,注意用整数方向与精确 叉积避免浮点判共线。