「EGOI2021」愤怒的牛 题解

题目大意

给定一个无向图，节点分为三类：

• 徒步区域 ($t_i = 1$)
• 未使用区域 ($t_i = 0$)
• 牛群区域 ($t_i = -1$)

需要在未使用区域中选择一些修建围墙，使得：

1. 牛群区域与徒步区域完全隔离
2. 所有徒步区域之间保持连通
3. 选择的围墙集合的偏远度最小（偏远度定义为集合中任意区域到最近徒步区域的最大距离）

算法思路

核心思想：二分答案 + 连通性检查

偏远度具有单调性：如果偏远度 $d$ 可行，那么所有 $> d$ 的偏远度都可行。因此可以二分答案。

算法步骤

1. 计算最短距离

   • 使用 Dijkstra 算法，以所有徒步区域为起点
   • 计算每个节点到最近徒步区域的距离 dis[i]

2. 二分偏远度

   • 收集所有未使用区域的距离值并排序去重
   • 二分查找最小的可行偏远度

3. 可行性检查 check(lim)

   • 标记候选围墙：所有未使用区域且 dis[i] ≤ lim 的节点
   • 检查隔离性：从所有牛群区域 BFS，不能到达任何徒步区域
   • 检查连通性：去除候选围墙后，所有徒步区域应在同一连通块

代码详解

数据结构

int n, m, tp[N], fa[N];
bool ans[N], vis[N];
ll dis[N];
vector<pair<int, int>> vt[N];  // 邻接表：<邻居, 边权>

关键函数

1. 并查集

int getf(int x) {
    return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

2. 可行性检查

bool check(ll lim) {
    // 标记候选围墙
    for (int i = 0; i < n; i++) {
        ans[i] = (tp[i] == 0 && dis[i] <= lim);
        vis[i] = false;
    }
    
    // BFS检查隔离性：从牛群区域出发
    queue<int> qu;
    for (int i = 0; i < n; i++)
        if (tp[i] == -1) {
            vis[i] = true;
            qu.push(i);
        }
    
    while (!qu.empty()) {
        int x = qu.front(); qu.pop();
        if (tp[x] == 1) return false;  // 到达徒步区域，不满足隔离
        
        if (ans[x]) continue;  // 遇到围墙就停止
        
        for (auto &[y, w] : vt[x])
            if (!vis[y]) {
                vis[y] = true;
                qu.push(y);
            }
    }
    
    // 检查徒步区域连通性
    for (int i = 0; i < n; i++) fa[i] = i;
    
    // 合并非围墙节点
    for (int i = 0; i < n; i++)
        if (!ans[i]) {
            for (auto &[x, w] : vt[i])
                if (!ans[x]) {
                    fa[getf(i)] = getf(x);
                }
        }
    
    // 检查所有徒步区域是否连通
    int id = -1;
    for (int i = 0; i < n; i++)
        if (tp[i] == 1) {
            if (id == -1) id = getf(i);
            else if (id != getf(i)) return false;
        }
    
    return true;
}

3. 主函数流程

int main() {
    // 输入
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &tp[i]);
    
    // 建图
    for (int i = 0; i < m; i++) {
        int x, y, w; scanf("%d%d%d", &x, &y, &w);
        x--, y--;
        vt[x].push_back({y, w});
        vt[y].push_back({x, w});
    }
    
    // Dijkstra计算最短距离
    memset(dis, 63, sizeof(dis));
    priority_queue<pair<ll, int>> pq;
    
    for (int i = 0; i < n; i++)
        if (tp[i] == 1) {
            dis[i] = 0;
            pq.push({0, i});
        }
    
    while (!pq.empty()) {
        ll w = -pq.top().F;
        int x = pq.top().S;
        pq.pop();
        if (w != dis[x]) continue;
        
        for (auto &[y, c] : vt[x])
            if (dis[y] > w + c) {
                dis[y] = w + c;
                pq.push({-dis[y], y});
            }
    }
    
    // 二分答案
    vector<ll> allv;
    for (int i = 0; i < n; i++)
        if (tp[i] == 0) allv.push_back(dis[i]);
    
    sort(allv.begin(), allv.end());
    allv.erase(unique(allv.begin(), allv.end()), allv.end());
    
    int l = 0, r = allv.size();
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(allv[mid])) r = mid;
        else l = mid + 1;
    }
    
    // 输出结果
    if (l >= allv.size()) {
        puts("-1");  // 无解
        return 0;
    }
    
    check(allv[l]);  // 最终标记答案
    vector<int> res;
    for (int i = 0; i < n; i++)
        if (ans[i]) res.push_back(i);
    
    printf("%d\n", res.size());
    for (auto &x : res) printf("%d ", x + 1);
    
    return 0;
}

复杂度分析

• Dijkstra：$O((n+m)\log n)$
• 二分：$O(\log n)$ 次检查
• 每次检查：$O(n+m)$ 的 BFS 和并查集操作
• 总复杂度：$O((n+m)\log^2 n)$，可接受 $3\times 10^5$ 的数据规模

算法正确性

1. 隔离性保证：从牛群区域 BFS，遇到围墙停止，确保牛无法到达徒步区域
2. 连通性保证：通过并查集检查所有徒步区域在去除围墙后仍连通
3. 最优性保证：二分找到最小的可行偏远度