把愉悦度化为 P 之和除以 MST 权值减树路径最大边,用 Kruskal 升序合并、并查集顺带维护分量最大 P,一次扫描覆盖所有点对。
OJ: roj
题目 ID: 1712
难度:提高
标签:最小生成树Kruskal并查集图论python
创建: 2026-10-07 17:45
更新: 2026-10-07 17:45
形式化题目
给定完全图
先从
求在所有生成树
数据范围:
正解
思路
直接枚举"哪棵生成树 + 哪条边"没有出路:一棵完全图的生成树有
第一步:固定点对,把
括号里就是含边
其中
于是答案化成
第二步:不用枚举点对。 若对每个点对都单独求
这就把"按点对枚举"换成了"按树边分组枚举":一条树边
结论:并查集在合并两个分量时顺带维护该分量内最大的
第三步:两次 Kruskal。 第一遍求 bestP 并逐边更新答案。因为记录顺序就是权值升序,不需要再排一次。
样例
| 合并顺序 | 合并的边 | 边权 |
涉及分量内的最大 |
||
|---|---|---|---|---|---|
| 1 | 1 | 199 | |||
| 2 | 1 | 199 | |||
| 3 | 198 | 2 |
第三步给出了 65.00,正是题面样例答案。第 3 步覆盖了
实现上有两个细节:Kruskal 的边表是
代码
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:45
# update_at: 2026-10-07 17:45
import sys
from itertools import combinations
from math import hypot
# 完全图的一条边:欧氏距离 + 两个端点下标。整个算法只操作这种三元组。
type EdgeList = list[tuple[float, int, int]]
def find(fa: list[int], x: int) -> int:
"""并查集查根,迭代 + 隔代路径压缩(N 可达 1000,避免递归)。"""
while fa[x] != x:
fa[x] = fa[fa[x]]
x = fa[x]
return x
def build_tree(n: int, edges: EdgeList) -> tuple[float, EdgeList]:
"""Kruskal:升序扫边,返回最小生成树总权值 W 与构成它的 N-1 条边。"""
fa = list(range(n))
total = 0.0
tree: EdgeList = []
for w, u, v in edges:
ru, rv = find(fa, u), find(fa, v)
if ru == rv:
continue # 两端已连通,这条边会成环
fa[ru] = rv
total += w
tree.append((w, u, v))
if len(tree) == n - 1:
break # 生成树已满,后面的边用不上
return total, tree
def max_pleasure(tree: EdgeList, total: float, p: list[int]) -> float:
"""按树边升序合并分量,求愉悦度 A/B 的最大值。
升序合并到边 e 时,跨越当前两个分量的所有点对,其在 MST 上的路径最大边
恰为 w(e),于是 B 的最小值 = W - w(e);这些点对里 A 最大的就是
两个分量各自最大的 P 之和。
"""
fa = list(range(len(p)))
best = list(p) # best[根] = 所在分量内最大的美味度 P
ans = 0.0
for w, u, v in tree:
a, b = find(fa, u), find(fa, v)
ratio = (best[a] + best[b]) / (total - w)
if ratio > ans:
ans = ratio
merged = best[a] if best[a] > best[b] else best[b]
fa[a] = b
best[b] = merged
return ans
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
pts: list[tuple[int, int, int]] = []
for _ in range(n):
x, y, q = next(data), next(data), next(data) # 题面的 x、y、P
pts.append((x, y, q))
# 完全图:每个点对一条边,权值取欧氏距离(排序后即为 Kruskal 的扫描顺序)
edges: EdgeList = sorted(
(hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1]), i, j)
for i, j in combinations(range(n), 2)
)
p = [q for _, _, q in pts] # 每家的美味度 P,下标与点编号一致
total, tree = build_tree(n, edges)
print(f"{max_pleasure(tree, total, p):.2f}")
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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:45
* update_at: 2026-10-07 17:45
*/
// 一本通 1712《汉堡店》
// ---------------------------------------------------------------------------
// 题意:完全图(边权 = 欧氏距离)上选一棵生成树 T,再选 T 中的一条边 (a,b)
// "吃光"两端,愉悦度 = A / B,其中 A = P_a + P_b,
// B = T 中除 (a,b) 外其余 N-2 条边的权值和 = W(T) - w(a,b)。求 A/B 最大值。
//
// 推导:
// 固定点对 (a,b),A 固定,要使 A/B 最大只需让 B 最小,即
// B_min(a,b) = min_{T ∋ (a,b)} ( W(T) - w(a,b) )
// = (含边 (a,b) 的最小生成树权值) - w(a,b).
// 记全图 MST 权值为 W。经典替换性质给出
// 含边 (a,b) 的最小生成树权值 = W + w(a,b) - maxEdgeOnMSTPath(a,b),
// 于 是 B_min(a,b) = W - maxEdgeOnMSTPath(a,b).
// ((a,b) 本身在 MST 上时路径就是这条边,B = W - w(a,b),与定义一致。)
//
// 接下来不再逐点对枚举,而是用「Kruskal 升序合并」一次性覆盖所有点对:
// 升序加边时,边 e=(u,v) 合并分量 A、B,则所有跨越 A、B 的点对 (u',v')
// 在 MST 上的路径最大边恰为 w(e)(路径上其余边都在更早、更小的权值里)。
// 同一个 w(e) 下,跨分量点对里 P 之和最大的一对就是
// maxP(A) + maxP(B)。故只需让并查集顺带维护每个分量的 maxP,
// 答案 = max_e ( maxP(A) + maxP(B) ) / ( W - w(e) ).
//
// 复杂度:完全图边数 O(N^2),排序 O(N^2 log N),第二遍合并 O(N α),空间 O(N^2)。
// N <= 1000 时约 5*10^5 条边,远低于 1000ms / 256MB。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // N <= 1000
const int MAXM = MAXN * (MAXN - 1) / 2 + 5; // 完全图边数上界
struct Point {
ll x, y; // 直角坐标
ll p; // 美味度 P
};
Point pt[MAXN];
struct Edge {
int u, v; // 两个端点
double w; // 欧氏距离
};
Edge edge[MAXM]; // 完全图边表
int ecnt;
struct TreeEdge {
int u, v; // MST 上的边,保存 Kruskal 的合并顺序(权值升序)
double w;
};
TreeEdge mst[MAXN]; // MST 恰有 N-1 条边
int fa[MAXN]; // 并查集
ll bestp[MAXN]; // bestp[根] = 该分量里最大的 P
// 按边权升序排序,供 Kruskal 使用
bool cmpEdge(const Edge &a, const Edge &b) {
return a.w < b.w;
}
int find(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]]; // 路径压缩(隔代压缩,迭代写法避免递归)
x = fa[x];
}
return x;
}
int main() {
int n;
if (scanf("%d", &n) != 1) return 0;
for (int i = 0; i < n; i++) {
scanf("%lld %lld %lld", &pt[i].x, &pt[i].y, &pt[i].p);
}
// 建完全图边表:每对点的欧氏距离
ecnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double dx = (double)(pt[i].x - pt[j].x);
double dy = (double)(pt[i].y - pt[j].y);
edge[ecnt].u = i;
edge[ecnt].v = j;
edge[ecnt].w = sqrt(dx * dx + dy * dy);
ecnt++;
}
}
sort(edge, edge + ecnt, cmpEdge);
// 第一遍 Kruskal:求最小生成树总权值 W,并按合并顺序记下 N-1 条树边
for (int i = 0; i < n; i++) fa[i] = i;
double W = 0.0;
int cnt = 0;
for (int k = 0; k < ecnt && cnt < n - 1; k++) {
int a = find(edge[k].u), b = find(edge[k].v);
if (a == b) continue; // 已成环,丢掉
fa[a] = b;
W += edge[k].w;
mst[cnt].u = edge[k].u;
mst[cnt].v = edge[k].v;
mst[cnt].w = edge[k].w;
cnt++;
}
// 第二遍:按同样的升序合并顺序,维护每个分量的最大 P,边走边更新答案
for (int i = 0; i < n; i++) {
fa[i] = i;
bestp[i] = pt[i].p;
}
double ans = 0.0;
for (int k = 0; k < cnt; k++) {
int a = find(mst[k].u), b = find(mst[k].v);
double B = W - mst[k].w; // 该权值下所有跨分量点对的最小 B
double cur = (double)(bestp[a] + bestp[b]) / B;
if (cur > ans) ans = cur;
// 合并分量,保留较大的 P
ll merged = bestp[a] > bestp[b] ? bestp[a] : bestp[b];
fa[a] = b;
bestp[b] = merged;
}
printf("%.2f\n", ans);
return 0;
}复杂度
- 时间:建完全图边表
,排序 ,两遍 Kruskal 均为 ,总计 。 时约 条边,C++ 实测最大测例 0.039 s(限时 1 s)。 - 空间:边表
个三元组,C++ 约 12 MB,峰值内存 9.8 MB(限时 256 MB);Python 用元组列表存边,最大测例实测峰值约 78 MB,仍在限制内。 - 与 C++ 解法的关系:两者是同一算法。C++ 用全局数组 +
sort+ 手写迭代并查集;Python 用itertools.combinations生成点对、内置sorted排序,并把"求 MST 权值"和"合并时统计答案"拆成两个函数。Python 侧最大测例实测 0.26 s,本题不存在明显的 TLE 风险。
总结
- 先消掉自由度最大的变量:原式里有一整棵生成树在变,看似要枚举
棵树;但固定点对后,"含某条边的最小生成树"立刻可以引用 MST 替换性质,树就被消成了一个数 。 - 替换性质的等价说法:
,即"最小分母 = MST 总权值减去路径最重边"。这一步把几何问题彻底变成了树上的路径统计。 - 用合并顺序代替树上路径查询:MST 上两点路径最大边,不必真的去树上跑倍增。Kruskal 升序合并时,每一条树边天然覆盖"恰好以它为分离点的所有点对",配合并查集维护的分量最大
,一次 扫描就覆盖了全部 个点对。 - 本题素材的可靠性备注:本仓库素材源的
data/由data.py自造(10 个点,含题面样例),题面来自网络重建而非官方原题文件。std.cpp采用"每个点 DFS 求树路径最大边"的做法,与本解思路同源;已实测该标程在全部 10 个数据点上与本解输出一致,且与 data/*.out全部吻合,故本题不存在"标程与题面不符"的问题。