题解：P12039 [USTCPC 2025] 高位逼抢

william1118 · 2025-10-20 12:48:00 · 题解

思路

设每个点的度数为 d_i，显然答案最大值就是 d_i（把这个点的所有边都堵死）。

那什么情况下答案可以减小呢，贪心的想，我们肯定是找到一个度数比该点小的且与该点有边相连的点，因为只有边数变小了，才能更好的把对方逼入绝境。

因此我们可以采用类似 dijkstra 的方式，用小根堆维护每个点的度数，如果遇到一个邻点，它的度数比当前的点的度数大，那么就可以用度数小的点去更新度数大的点，将度数大的点的度数减一再加入堆中，如此循环往复，直到每个点都被操作过为止。

::::success[AC 代码]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
using pii = pair<int, int>;

const int N = 1e6 + 1;

int n, m, d[N], b[N];
vector<int> e[N];

int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        d[u]++, d[v]++;
    }
    priority_queue<pii, vector<pii>, greater<>> q;
    for (int i = 1; i <= n; i++) {
        q.emplace(d[i], i);
    }
    while (q.size()) {
        int deg = q.top().first, u = q.top().second;
        q.pop();
        if (b[u]) continue;
        b[u] = 1;
        for (int v : e[u]) {
            if (d[v] > deg) {
                d[v]--;
                q.emplace(d[v], v);
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << d[i] << ' ';
    return 0;
}

::::