消防站选址问题题解

题目理解

我们有一个包含 $n$ 个村庄的树形网络，需要在其中选择 $f$ 个村庄建立消防站，使得所有村庄到最近消防站的最大距离最小化。

关键点：

• 道路网络是一棵树（任意两点间有唯一路径）
• 响应时间 = 沿着唯一路径的行驶时间总和
• 目标：最小化最坏情况下的响应时间

问题转化

这是一个典型的最小化最大距离问题，可以抽象为：在树中选择 $f$ 个点作为中心，使得所有点到最近中心的距离的最大值最小。

算法思路

方法：二分答案 + 贪心验证

1. 二分答案框架

• 下界：0（当 $f = n$ 时，每个村庄都有消防站）
• 上界：树的直径（最远两点的距离）
• 对于每个候选值 $mid$，检查是否能用 $f$ 个消防站覆盖整棵树，使得所有点到最近消防站距离 ≤ $mid$

2. 验证函数设计

使用树形贪心策略：

bool check(int limit) {
    int stations_needed = 0;
    // 从叶子节点向上处理，返回当前节点到最近消防站的距离
    // 如果距离 > limit，则在当前节点放置消防站
}

贪心规则：

1. 深度优先遍历（后序遍历）
2. 对于每个节点，维护两个值：
   • max_uncovered：子树中未被覆盖的最远节点到当前节点的距离
   • min_covered：子树中最近消防站到当前节点的距离
3. 当 max_uncovered + min_covered > limit 时，需要在当前节点放置消防站

3. 核心贪心策略

pair<int, int> dfs(int u, int parent, int limit) {
    int max_uncovered = 0;  // 未被覆盖的最远距离
    int min_covered = INF;  // 最近消防站距离
    
    for (每条边 (u, v) with weight w) {
        if (v == parent) continue;
        
        auto [child_uncovered, child_covered] = dfs(v, u, limit);
        
        if (child_covered + w <= limit) {
            min_covered = min(min_covered, child_covered + w);
        } else {
            max_uncovered = max(max_uncovered, child_uncovered + w);
        }
    }
    
    // 决策：是否需要在此放置消防站
    if (max_uncovered + min_covered <= limit) {
        return {0, min_covered};
    }
    if (max_uncovered >= limit) {
        stations_needed++;
        return {0, 0};  // 当前节点新建消防站
    }
    return {max_uncovered, min_covered};
}

完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
const int INF = 1e9;

struct Edge {
    int to, weight;
};

vector<Edge> graph[MAXN];
int n, f;
int stations_needed;

pair<int, int> dfs(int u, int parent, int limit) {
    int max_uncovered = 0;  // 子树中未被覆盖的最远距离
    int min_covered = INF;  // 子树中最近消防站的距离
    
    for (auto& edge : graph[u]) {
        int v = edge.to, w = edge.weight;
        if (v == parent) continue;
        
        auto [child_uncovered, child_covered] = dfs(v, u, limit);
        
        if (child_covered != INF && child_covered + w <= limit) {
            // 子节点有消防站且能覆盖到当前节点
            min_covered = min(min_covered, child_covered + w);
        } else {
            // 子节点无法提供覆盖，更新未被覆盖的距离
            max_uncovered = max(max_uncovered, child_uncovered + w);
        }
    }
    
    // 如果当前节点本身需要被覆盖
    if (max_uncovered + min_covered <= limit) {
        // 可以被现有消防站覆盖
        return {0, min_covered};
    }
    
    if (max_uncovered >= limit) {
        // 必须在此建立消防站
        stations_needed++;
        return {0, 0};
    }
    
    // 继续向上传递未被覆盖的距离
    return {max_uncovered, (min_covered == INF) ? INF : min_covered};
}

bool canCover(int limit) {
    stations_needed = 0;
    auto result = dfs(1, -1, limit);
    
    // 如果根节点还有未被覆盖的距离，需要额外消防站
    if (result.first > 0) {
        stations_needed++;
    }
    
    return stations_needed <= f;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> f;
    
    int max_edge = 0;
    for (int i = 2; i <= n; i++) {
        int v, t;
        cin >> v >> t;
        graph[i].push_back({v, t});
        graph[v].push_back({i, t});
        max_edge = max(max_edge, t);
    }
    
    // 二分答案
    int left = 0, right = n * max_edge;  // 上界为最坏情况
    int answer = right;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canCover(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \log(\text{树的直径}))$
  • 二分答案：$O(\log(\text{上界}))$
  • 每次验证：$O(n)$ 的DFS
• 空间复杂度：$O(n)$ 用于存储树结构

算法正确性证明

1. 贪心选择正确性：从叶子节点向上处理，确保在不得不放置消防站时才放置，这是最优的
2. 二分答案正确性：如果距离 $d$ 可行，那么所有 $> d$ 的距离也可行，满足单调性
3. 覆盖完整性：算法确保所有节点要么被现有消防站覆盖，要么通过新建消防站覆盖

样例验证

样例1：

• 输入：6个村庄，2辆消防车
• 树结构形成较长的路径
• 最优解：在关键位置放置2个消防站，最大响应时间8

样例2：

• 输入：3个村庄，3辆消防车
• 每个村庄都有消防站，响应时间0

总结

本题通过二分答案将优化问题转化为判定问题，再通过树形贪心高效验证解的可行性。这种"二分+验证"的思路在解决最小化最大值问题时非常有效，是竞赛中的经典技巧。