扩散

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1343 字
曼哈顿距离最小生成树的最大边折半
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1437
// 题意：平面上 n 个点同时向四方向以单位速度扩散成菱形，求最早什么时刻所有点的扩散区域连成一个连通块。
// 思路：最小生成树 + 曼哈顿距离。
// 1. 两点连通的条件是曼哈顿距离不超过 2t，即 t >= dist / 2。
// 2. 整个点集连通的最早时刻由「瓶颈」决定：先求曼哈顿距离完全图的最小生成树。
// 3. 答案为生成树上最大边 (maxEdge + 1) / 2 向上取整。
// 复杂度：O(n^2 log n) 时间 / O(n^2) 空间
// 易错点：扩散是菱形（曼哈顿距离），不是圆（欧氏距离），两点在 t 时刻的菱形相交条件是曼哈顿距离 <= 2t。
// 易错点：答案要向上取整，写成 (maxEdge + 1) / 2 的整数除法，直接用 maxEdge / 2 会少 1。
#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int u, v;
    long long w;
};
vector<int> fa;
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<long long> x(n), y(n);
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    vector<Edge> e;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            e.push_back({i, j, llabs(x[i] - x[j]) + llabs(y[i] - y[j])});
        }
    }
    sort(e.begin(), e.end(), [](const Edge& a, const Edge& b){
        return a.w < b.w;
    });
    fa.resize(n);
    for(int i = 0; i < n; i++) fa[i] = i;
    long long maxEdge = 0;
    int cnt = 0;
    for(const Edge& ed : e){
        int fu = find(ed.u), fv = find(ed.v);
        if(fu == fv) continue;
        fa[fu] = fv;
        maxEdge = ed.w;
        if(++cnt == n - 1) break;
    }
    cout << (maxEdge + 1) / 2 << "\n";
    return 0;
}
扩散

正文

一本通·提高篇的其它内容
