ACGO巅峰赛#30 T6

参考༺ཌ融合版爱好者——改歌神ༀད༻。如果有侵权，还请联系删除，十分感谢

题解：雾港城的服务中心

题目描述：

雾港城要在路网中建立两座服务中心。城市的路网是一个树结构，具有 n 个路口和 n-1 条双向道路。我们的目标是选择两个节点作为服务中心，要求使得所有其他节点到最近服务中心的距离尽可能小，并求出该最小最慢响应距离。

思路分析

这道题的核心是树的直径和服务中心的选择。通过树的直径，我们可以确定两个中心的最佳选择，从而最小化每个节点到最近中心的距离。

步骤分析

1. 树的直径：

   • 树的直径是树中任意两点之间的最远距离，它可以通过两次 BFS 来确定。
   • 首先从任意一个节点（比如节点 1）开始，进行 BFS 找到最远的节点 A。
   • 然后，从节点 A 开始，进行一次 BFS，找到最远的节点 B。这两个节点 A 和 B 就是树的直径的端点。

2. 选择两个服务中心：

   • 最优的两个服务中心可以选择为树的直径的两个端点（A 和 B）。
   • 这样做的原因是，树的直径上的节点的距离最大，通过将服务中心放在这两个端点，能尽量减少最远节点到服务中心的距离。

3. 计算最慢响应距离：

   • 我们需要找到一个最小的响应距离 R，使得所有节点到两个中心的距离都不超过 R。
   • 对于每个节点，计算它到两个服务中心的最小距离，并检查是否所有节点都能满足最慢响应距离 R 的要求。

4. 优化方法：

   • 我们使用二分查找来优化最慢响应距离 R，通过检查 R 是否满足条件来确定最小的响应距离。
   • 对于每一个候选的响应距离 R，我们检查是否能够安排服务中心使得每个节点到最近的中心的距离都不超过 R。

代码实现

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

const int MAXN = 200005;
vector<int> g[MAXN];

// BFS 返回最远节点及其距离
pair<int, int> bfs(int start, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    int farthest_node = start, max_dist = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > max_dist) {
                    max_dist = dist[v];
                    farthest_node = v;
                }
            }
        }
    }
    return {farthest_node, max_dist};
}

// 获取从 start 到 end 的路径，并记录每个节点的位置
vector<int> getPath(int start, int end, int n, vector<int>& pos) {
    vector<int> parent(n + 1, -1);
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }

    vector<int> path;
    for (int u = end; u != -1; u = parent[u]) {
        path.push_back(u);
    }
    reverse(path.begin(), path.end());

    for (int i = 0; i < path.size(); ++i) {
        pos[path[i]] = i;
    }

    return path;
}

// 二分查找最小的响应距离
bool check(int R, vector<int>& pos, vector<int>& need, vector<int>& diam, int dr) {
    vector<pair<double, double>> intervals;
    for (int u : diam) {
        if (need[u] > R) {
            return false;
        }
        double d = R - need[u];
        double left = pos[u] - d;
        double right = pos[u] + d;
        left = max(left, 0.0);
        right = min(right, (double)dr);
        if (left > right) {
            return false;
        }
        intervals.push_back({left, right});
    }

    sort(intervals.begin(), intervals.end());

    auto isValid = [](const vector<pair<double, double>>& intervals) -> bool {
        if (intervals.empty()) return true;
        double max_left = intervals[0].first, min_right = intervals[0].second;
        for (const auto& p : intervals) {
            max_left = max(max_left, p.first);
            min_right = min(min_right, p.second);
            if (max_left > min_right) {
                return false;
            }
        }
        return max_left <= min_right;
    };

    if (isValid(intervals)) return true;
    
    // 尝试删除一部分区间
    for (int i = 0; i < min(2, (int)intervals.size()); ++i) {
        for (int type = 0; type < 2; ++type) {
            double A = (type == 0) ? intervals[i].first : intervals[i].second;
            vector<pair<double, double>> new_intervals;
            for (const auto& p : intervals) {
                if (p.first <= A + 1e-9 && A <= p.second + 1e-9) {
                    // 合并
                } else {
                    new_intervals.push_back(p);
                }
            }
            if (isValid(new_intervals)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (n <= 2) {
        cout << "0";
        return 0;
    }

    // 1. 通过两次BFS计算树的直径
    int d1 = bfs(1, n).first;
    int d2 = bfs(d1, n).first;

    vector<int> pos(n + 1, -1);
    vector<int> diam = getPath(d1, d2, n, pos);
    int m = diam.size();
    int dr = m - 1;

    // 2. 计算每个节点需要的距离
    vector<int> need(n + 1, 0);
    vector<bool> vis(n + 1, false);
    for (int u : diam) {
        vis[u] = true;
    }

    for (int u : diam) {
        for (int v : g[u]) {
            if (vis[v]) continue;
            queue<pair<int, int>> q;
            q.push({v, 1});
            vis[v] = true;
            int mh = 1;
            while (!q.empty()) {
                auto [cur, d] = q.front();
                q.pop();
                mh = max(mh, d);
                for (int w : g[cur]) {
                    if (!vis[w]) {
                        vis[w] = true;
                        q.push({w, d + 1});
                    }
                }
            }
            need[u] = max(need[u], mh);
        }
    }

    // 3. 二分查找最小响应距离
    int lo = 0, hi = dr;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(mid, pos, need, diam, dr)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    cout << lo;
    return 0;
}

题解说明：

1. 树的构建与输入：

   • 通过邻接表存储树的图形表示。

2. 直径计算：

   • 使用 BFS 计算树的直径。两次 BFS 能够找到树的两个最远节点，这两个节点即为服务中心的候选点。

3. 路径与位置记录：

   • 通过 BFS 获取树的直径路径，并记录路径中每个节点的位置，以便计算响应距离。

4. 最慢响应距离计算：

   • 对于每个节点，通过二分查找最小的最慢响应距离 R，并使用区间覆盖技巧判断是否能够满足响应距离。

时间复杂度：

• 每次 BFS 的时间复杂度为 O(n)。
• 二分查找的最大次数为 O(log n)，每次判断的时间复杂度为 O(n)，因此整体时间复杂度为 O(n log n)，适用于最大 n = 200000 的情况。

总结：

这个算法通过树的直径和二分查找来优化最慢响应距离问题，能够高效地解决大规模输入的情况。