#5482. 「UOI 2016 Stage 4 Day1」地铁 题解

问题分析

地铁网络是一个树结构（最小连通图），车站的进站费用实际上是该节点在树中的偏心率（eccentricity），即从该节点到其他所有节点的最大距离。

我们需要构造一棵树，使得：

1. 所有喜欢的数字都出现在偏心率集合中
2. 所有讨厌的数字都不出现在偏半径集合中
3. 车站数量最少

关键观察

1. 树的偏心率性质

对于一棵树：

• 最小偏心率 = 树的半径 $r$
• 最大偏心率 = 树的直径 $d$
• 所有偏心率值在区间 $[r, d]$ 内，且包含所有中间值

2. 直径与半径的关系

对于有 $n$ 个节点的树：

• 直径 $d$ 和半径 $r$ 满足：$r = \lceil d/2 \rceil$
• 所有偏心率值在 $[r, d]$ 范围内连续出现

算法思路

步骤1：处理约束条件

设喜欢的数字集合为 $A$，讨厌的数字集合为 $B$。

我们需要找到最小的 $n$，使得存在直径 $d$ 满足：

1. $[r, d]$ 包含所有 $A_i$，其中 $r = \lceil d/2 \rceil$
2. $[r, d]$ 不包含任何 $B_i$

步骤2：寻找最小直径

对于候选直径 $d$：

• 计算半径 $r = \lceil d/2 \rceil$
• 检查区间 $[r, d]$ 是否包含所有 $A_i$ 且不包含任何 $B_i$
• 满足条件的最小 $d$ 对应最少节点数 $n = d + 1$

步骤3：节点数计算

对于直径 $d$ 的树，最少节点数为 $d + 1$（路径图）

代码实现

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

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> like(N), hate(M);
    for (int i = 0; i < N; i++) cin >> like[i];
    for (int i = 0; i < M; i++) cin >> hate[i];
    
    // 找到喜欢的数字中的最大值和最小值
    int max_like = *max_element(like.begin(), like.end());
    int min_like = *min_element(like.begin(), like.end());
    
    // 检查讨厌的数字是否在可能范围内
    for (int b : hate) {
        if (b >= min_like && b <= max_like) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    // 最小直径至少是最大喜欢的数字
    int d = max_like;
    while (true) {
        int r = (d + 1) / 2;  // 上取整
        
        // 检查区间 [r, d] 是否包含所有喜欢的数字
        bool valid = true;
        for (int a : like) {
            if (a < r || a > d) {
                valid = false;
                break;
            }
        }
        
        // 检查区间是否不包含讨厌的数字
        if (valid) {
            for (int b : hate) {
                if (b >= r && b <= d) {
                    valid = false;
                    break;
                }
            }
        }
        
        if (valid) {
            cout << d + 1 << endl;  // 直径d的路径图有d+1个节点
            return 0;
        }
        
        d++;
        
        // 设置一个合理的上限，避免无限循环
        if (d > 1000000) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    return 0;
}

复杂度分析

• 预处理：$O(N + M)$
• 直径搜索：最坏情况 $O(\text{max\_like})$，但实际收敛很快
• 总复杂度：可接受范围内

样例验证

样例1

输入: N=2, M=3, like=[4,7], hate=[13,1,3]

计算:
- 最小直径至少为7
- d=7: r=4, 区间[4,7]包含4,7，不包含13,1,3 ✓
- 最少节点数 = 7 + 1 = 8
输出: 8

样例2

输入: N=2, M=1, like=[4,7], hate=[6]

计算:
- 最小直径至少为7
- d=7: r=4, 区间[4,7]包含6 ✗
- d=8: r=4, 区间[4,8]包含6 ✗
- d=9: r=5, 区间[5,9]不包含4 ✗
- 无法满足条件
输出: -1

优化改进

对于大数据范围，可以更高效地确定最小直径：

// 优化版本的核心逻辑
int find_min_diameter(const vector<int>& like, const vector<int>& hate) {
    int max_a = *max_element(like.begin(), like.end());
    int min_a = *min_element(like.begin(), like.end());
    
    // 检查基本可行性
    for (int b : hate) {
        if (b >= min_a && b <= max_a) return -1;
    }
    
    // 最小直径下界
    int lower = max_a;
    // 最小直径上界
    int upper = max(2 * min_a - 1, max_a);
    
    for (int d = lower; d <= upper + 100; d++) {
        int r = (d + 1) / 2;
        
        if (r > min_a) continue;  // 半径不能大于最小喜欢值
        
        bool valid = true;
        for (int a : like) {
            if (a < r || a > d) {
                valid = false;
                break;
            }
        }
        if (!valid) continue;
        
        for (int b : hate) {
            if (b >= r && b <= d) {
                valid = false;
                break;
            }
        }
        if (valid) return d;
    }
    
    return -1;
}

总结

本题的关键在于理解：

1. 树结构中偏心率值的连续分布特性
2. 直径与半径的数学关系
3. 路径图是实现特定偏心率集合的最优结构

算法通过枚举可能的直径，检查偏心率区间的包含关系，找到满足约束的最小车站数。