跳转至

ATC & CF 选做(23May,23Jun)

给你一张 \(n\) 个点 \(m\) 条边的无权无向图，节点 \(p_i\) 上会有一个体力值为 \(h_i\) 的守卫，守卫有 \(k\) 个。

一个节点被看守，当且仅当存在一个守卫，使得这个守卫可以移动到这个节点上，且剩余体力大于等于零。

移动一条边需要花费 \(1\) 的体力。

求出所有的被看守的节点。

\(n, m \le 2e5, 1\le k \le n\)。

注意到问题关键在于守卫。

不妨考虑从守卫开始扩展，即对于每个守卫 BFS 或者 Dij 之类的做一遍。

但是这样复杂度是 \(O(nm)\) 甚至更高的。

经过观察之后也找不到其它性质或者是别的做法。

所以考虑怎么优化。

可以考虑每次找到剩余体力最大的守卫，类似 dij 更新周围的节点。

但是守卫是不能分身的，于是我们记录一个 \(mx\) 表示所有守卫到达这个节点，所剩余的体力最大值。

然后每次找到最大的 mx 来更新即可。

过程类似 dij.

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// author : black_trees

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n, m, k;
int tot = 0, head[si];
struct Edge { int ver, Next; } e[si << 1];
inline void add(int u, int v) { e[tot] = (Edge){v, head[u]}, head[u] = tot++; } 

int p[si], h[si];

std::vector<int> c;
int ans = 0, mx[si];
std::priority_queue<std::pair<int, int>> q;

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    memset(head, -1, sizeof head);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }

    memset(mx, -1, sizeof head);
    for(int i = 1; i <= k; ++i)
        cin >> p[i] >> h[i];
    for(int i = 1; i <= k; ++i) 
        if(mx[p[i]] < h[i]) q.push(make_pair(mx[p[i]] = h[i], p[i]));

    while(!q.empty()) {
        auto [val, u] = q.top();
        q.pop();
        if(mx[u] != val) continue;
        for(int i = head[u]; ~i; i = e[i].Next) {
            int v = e[i].ver;
            if(mx[v] < val - 1) q.push(make_pair(mx[v] = val - 1, v));
        }
    }

    c.clear();
    for(int i = 1; i <= n; ++i)
        if(~mx[i]) c.emplace_back(i);
    cout << c.size() << endl;
    for(auto x : c) cout << x << " ";
    cout << endl;

    return 0;
}
最后更新: June 17, 2023