汉堡店

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

把愉悦度化为 P 之和除以 MST 权值减树路径最大边,用 Kruskal 升序合并、并查集顺带维护分量最大 P,一次扫描覆盖所有点对。

OJ: roj

题目 ID: 1712

难度:提高

标签:最小生成树Kruskal并查集图论python

创建: 2026-10-07 17:45

更新: 2026-10-07 17:45

形式化题目

给定完全图 G=(V,E)G = (V, E),∣V∣=N|V| = N,点 ii 带坐标 (xi,yi)(x_i, y_i) 与美味度 PiP_i,边 (i,j)(i, j) 的权值为两点欧氏距离 w(i,j)=(xi−xj)2+(yi−yj)2w(i,j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}。

先从 GG 中取出任意一棵生成树 TT(N−1N - 1 条边),再从 TT 中挑一条边 (a,b)(a, b) 把两端"吃光",得到的愉悦度为

AB,A=Pa+Pb,B=∑e∈T,  e≠(a,b)w(e)=W(T)−w(a,b).\frac{A}{B}, \qquad A = P_a + P_b, \qquad B = \sum_{e \in T,\; e \neq (a,b)} w(e) = W(T) - w(a,b).

求在所有生成树 TT 与所有树边 (a,b)(a,b) 的选择下 AB\dfrac{A}{B} 能取到的最大值,保留两位小数。

数据范围:2<N⩽10002 < N \leqslant 1000,0⩽x,y⩽10000 \leqslant x, y \leqslant 1000,0<P<100000 < P < 10000。

正解

思路

直接枚举"哪棵生成树 + 哪条边"没有出路:一棵完全图的生成树有 NN−2N^{N-2} 种,N=1000N = 1000 时天文数字。必须先把 TT 从这个式子里消掉。

第一步:固定点对,把 TT 的最优值算出来。 对固定的 (a,b)(a, b),分子 A=Pa+PbA = P_a + P_b 是常数,要让 AB\dfrac{A}{B} 最大只需让分母 BB 最小。而 B=W(T)−w(a,b)B = W(T) - w(a,b),所以

Bmin⁡(a,b)=(min⁡T∋(a,b)W(T))−w(a,b).B_{\min}(a,b) = \Big(\min_{T \ni (a,b)} W(T)\Big) - w(a,b).

括号里就是含边 (a,b)(a,b) 的最小生成树权值。设原图的 MST 权值为 WW,经典替换性质(加边成环、删环上最重边仍得最优树)给出

Bmin⁡(a,b)=W−mx(a,b),B_{\min}(a,b) = W - \mathrm{mx}(a,b),

其中 mx(a,b)\mathrm{mx}(a,b) 表示 MST 上 aa 到 bb 的路径中最大的边权。当 (a,b)(a,b) 本身就在 MST 上时,路径就是这条边,B=W−w(a,b)B = W - w(a,b),与定义完全一致。

于是答案化成

ans=max⁡a<bPa+PbW−mx(a,b).\text{ans} = \max_{a < b} \frac{P_a + P_b}{W - \mathrm{mx}(a,b)}.

第二步:不用枚举点对。 若对每个点对都单独求 mx(a,b)\mathrm{mx}(a,b),代价是 O(N3)O(N^3) 或 O(N2log⁡N)O(N^2 \log N) 带一个树上倍增。但注意一个关键性质:在 Kruskal 按边权升序处理的过程中,当边 e=(u,v)e = (u,v) 第一次把两个分量 SuS_u、SvS_v 连起来时,所有横跨这两个分量的点对 (u′,v′)(u', v') 在 MST 上的路径最大边恰好是 w(e)w(e)——因为路径上除 ee 以外的边都在更早、更小的权值中,否则这两个分量早就被连上了。

这就把"按点对枚举"换成了"按树边分组枚举":一条树边 ee 一次性覆盖了 ∣Su∣⋅∣Sv∣|S_u| \cdot |S_v| 个点对,而这些点对的 Bmin⁡B_{\min} 全都等于同一个值 W−w(e)W - w(e)。分子要最大,只需让 Pu′+Pv′P_{u'} + P_{v'} 在这批点对里取最大,也就是

max⁡u′∈Su, v′∈Sv(Pu′+Pv′)=max⁡u′∈SuPu′+max⁡v′∈SvPv′.\max_{u' \in S_u,\, v' \in S_v} (P_{u'} + P_{v'}) = \max_{u' \in S_u} P_{u'} + \max_{v' \in S_v} P_{v'}.

结论:并查集在合并两个分量时顺带维护该分量内最大的 PP 即可,答案更新式为

ans←max⁡(ans, bestP(Su)+bestP(Sv)W−w(e)).\text{ans} \leftarrow \max\Big(\text{ans},\ \frac{\mathrm{bestP}(S_u) + \mathrm{bestP}(S_v)}{W - w(e)}\Big).

第三步:两次 Kruskal。 第一遍求 WW 并把 MST 的 N−1N-1 条边按合并顺序记下来;第二遍用同样的顺序重新合并、维护 bestP 并逐边更新答案。因为记录顺序就是权值升序,不需要再排一次。

样例 (1,1,20),(1,2,30),(200,2,80),(200,1,100)(1,1,20), (1,2,30), (200,2,80), (200,1,100) 的 MST 是 {(1,2),(3,4),(2,3)}\{(1,2), (3,4), (2,3)\},权值 1+1+198=2001 + 1 + 198 = 200。升序合并的三步是:

合并顺序 合并的边 边权 ww 涉及分量内的最大 PP B=W−wB = W - w A/BA/B
1 (1,2)(1,2) 1 30,2030, 20 199 50/199≈0.2550/199 \approx 0.25
2 (3,4)(3,4) 1 100,80100, 80 199 180/199≈0.90180/199 \approx 0.90
3 (2,3)(2,3) 198 {1,2}\{1,2\} 内 3030,{3,4}\{3,4\} 内 100100 2 130/2=65130/2 = 65

第三步给出了 65.00,正是题面样例答案。第 3 步覆盖了 2×2=42 \times 2 = 4 个跨分量点对,其中 (2,4)(2,4) 的 PP 之和最大,与题面提示里"选择 (2,4)(2,4)"的选择一致。

实现上有两个细节:Kruskal 的边表是 O(N2)O(N^2) 的浮点三元组,N=1000N = 1000 时约 50 万条边,用全局数组即可;并查集用迭代 + 路径压缩而非递归,避免 N=1000N = 1000 的链在压缩时爆栈。

代码

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: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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:建完全图边表 O(N2)O(N^2),排序 O(N2log⁡N)O(N^2 \log N),两遍 Kruskal 均为 O(N2α(N))O(N^2 \alpha(N)),总计 O(N2log⁡N)O(N^2 \log N)。N=1000N = 1000 时约 5×1055 \times 10^5 条边,C++ 实测最大测例 0.039 s(限时 1 s)。
  • 空间:边表 O(N2)O(N^2) 个三元组,C++ 约 12 MB,峰值内存 9.8 MB(限时 256 MB);Python 用元组列表存边,最大测例实测峰值约 78 MB,仍在限制内。
  • 与 C++ 解法的关系:两者是同一算法。C++ 用全局数组 + sort + 手写迭代并查集;Python 用 itertools.combinations 生成点对、内置 sorted 排序,并把"求 MST 权值"和"合并时统计答案"拆成两个函数。Python 侧最大测例实测 0.26 s,本题不存在明显的 TLE 风险。

总结

  • 先消掉自由度最大的变量:原式里有一整棵生成树在变,看似要枚举 NN−2N^{N-2} 棵树;但固定点对后,"含某条边的最小生成树"立刻可以引用 MST 替换性质,树就被消成了一个数 WW。
  • 替换性质的等价说法:Bmin⁡(a,b)=W−mx(a,b)B_{\min}(a,b) = W - \mathrm{mx}(a,b),即"最小分母 = MST 总权值减去路径最重边"。这一步把几何问题彻底变成了树上的路径统计。
  • 用合并顺序代替树上路径查询:MST 上两点路径最大边,不必真的去树上跑倍增。Kruskal 升序合并时,每一条树边天然覆盖"恰好以它为分离点的所有点对",配合并查集维护的分量最大 PP,一次 O(N2α)O(N^2 \alpha) 扫描就覆盖了全部 (N2)\binom{N}{2} 个点对。
  • 本题素材的可靠性备注:本仓库素材源的 data/ 由 data.py 自造(10 个点,含题面样例),题面来自网络重建而非官方原题文件。std.cpp 采用"每个点 DFS 求树路径最大边"的 O(N2)O(N^2) 做法,与本解思路同源;已实测该标程在全部 10 个数据点上与本解输出一致,且与 data/*.out 全部吻合,故本题不存在"标程与题面不符"的问题。