牛之国

[牛客链接](https://www.nowcoder.com/practice/98cd1d48b86943e487c7148cf5fca714)

思路

所有城市同时向所有其他城市派出施工队，速度为 1，两支施工队碰头即连通。对于城市 和城市 ，双方各派一支队伍沿最短路线相向而行，经过 年后碰头。因此在时刻 ，两座城市连通当且仅当 。

问题转化为：找到最小的 ，使得以 为阈值的距离图是连通的。这正是最小生成树的瓶颈边问题——对所有城市对建边，用 Kruskal 求 MST，答案就是 MST 中最长边除以 2 再向上取整。

为什么是瓶颈边？ MST 的一个经典性质：将所有边按权值从小到大加入，第一次使图连通的那条边（即 MST 最大边）就是使全图连通所需的最小阈值。这恰好对应"所有城市最早全部连通"的时刻。

避免浮点误差： 排序时使用距离的平方（整数），最后求答案时用二分：找最小整数 满足 ，即 。乘法可能溢出 long long，C++ 中用 __int128，Java 中用 BigInteger。

以样例 1 为例：

三座城市 ，距离分别为 。MST 选择边 和 ，瓶颈边为 ，答案 。

代码

#include <bits/stdc++.h>
using namespace std;

int fa[5005];

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

bool unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    fa[a] = b;
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; i++) scanf("%lld%lld", &x[i], &y[i]);

    vector<tuple<long long, int, int>> edges;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            edges.push_back({dx * dx + dy * dy, i, j});
        }
    sort(edges.begin(), edges.end());

    for (int i = 0; i < n; i++) fa[i] = i;

    long long maxD2 = 0;
    int cnt = 0;
    for (auto& [d2, u, v] : edges) {
        if (unite(u, v)) {
            maxD2 = d2;
            if (++cnt == n - 1) break;
        }
    }

    long long lo = 0, hi = 2000000000LL;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if ((__int128)4 * mid * mid >= (__int128)maxD2)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%lld\n", lo);
    return 0;
}

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
    static int[] fa;

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

    static boolean unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        fa[a] = b;
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        long[] x = new long[n], y = new long[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            x[i] = Long.parseLong(st.nextToken());
            y[i] = Long.parseLong(st.nextToken());
        }

        int m = n * (n - 1) / 2;
        long[] dist2 = new long[m];
        int[] eu = new int[m], ev = new int[m];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long dx = x[i] - x[j], dy = y[i] - y[j];
                dist2[idx] = dx * dx + dy * dy;
                eu[idx] = i;
                ev[idx] = j;
                idx++;
            }
        }

        Integer[] order = new Integer[m];
        for (int i = 0; i < m; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Long.compare(dist2[a], dist2[b]));

        fa = new int[n];
        for (int i = 0; i < n; i++) fa[i] = i;

        long maxD2 = 0;
        int cnt = 0;
        for (int k = 0; k < m; k++) {
            int e = order[k];
            if (unite(eu[e], ev[e])) {
                maxD2 = dist2[e];
                if (++cnt == n - 1) break;
            }
        }

        long lo = 0, hi = 2000000000L;
        BigInteger target = BigInteger.valueOf(maxD2);
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            BigInteger lhs = BigInteger.valueOf(4).multiply(BigInteger.valueOf(mid)).multiply(BigInteger.valueOf(mid));
            if (lhs.compareTo(target) >= 0)
                hi = mid;
            else
                lo = mid + 1;
        }
        System.out.println(lo);
    }
}

复杂度

  • 时间复杂度：，建 条边并排序，并查集操作近似 。
  • 空间复杂度：，存储所有边。