专栏文章

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

wwilliam1118
P12039题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mink3agx
此快照首次捕获于
2025/12/02 03:42
3 个月前
此快照最后确认于
2025/12/02 03:42
3 个月前
查看原文

思路

设每个点的度数为 did_i，显然答案最大值就是 did_i（把这个点的所有边都堵死）。
那什么情况下答案可以减小呢，贪心的想，我们肯定是找到一个度数比该点小的且与该点有边相连的点，因为只有边数变小了，才能更好的把对方逼入绝境。
因此我们可以采用类似 dijkstra 的方式，用小根堆维护每个点的度数，如果遇到一个邻点，它的度数比当前的点的度数大，那么就可以用度数小的点去更新度数大的点，将度数大的点的度数减一再加入堆中，如此循环往复，直到每个点都被操作过为止。
AC 代码CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...