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

mairuisheng · 2025-06-13 13:40:40 · 题解

• 题目：P12039 [USTCPC 2025] 高位逼抢

• 主要算法：拓扑排序。

• 题意：

题意很清楚了（见题目形式化题面）：

一个 n 个点 m 条边的无向图（无重边自环），一个棋子，还有一个常数 x。A 和 B 玩一个游戏。

初始棋子位于 i 节点，此后每一回合：

• B 选定至多 x 条边删掉
• A 把棋子沿着某条边移到另一个节点
• B 把刚刚删掉的边复原

如果 A，B 都绝顶聪明，并且在有限轮中，B 可以把 A 逼入绝境（无法移动），则 B 胜利，否则 A 胜利。

对于 i\in[1,n] 求 x 至少为多少，B 才胜利。

• 分析：

设 ans_i 为第 i 个节点的答案。显然，ans_i 要初始化为节点 i 的出度，因为将 i 节点的出边全部删除，棋子就无法移动了。

但是，这时的答案肯定不是最优的，所以，我们要减小 ans_i 以此得到最优解。

我们发现出度最小的点已经是最优解了，因为无法用一个比它出度更小的节点更新它。于是，我们可以用一个出度小的节点更新一个出度大的节点。

我们用 set（或用 priority_queue）维护，每次取出出度最小的节点 i，用 i 更新它的子节点 j，如果 ans_j>ans_i，就在集合中删除 j，将 ans_j 赋值为 ans_j-1，最后插回集合。

• 时间复杂度：O(n \log m)。

• 参考代码：

//#pragma GCC optimize(3)
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char s;
    s=getchar();
    while(s<48||s>57)
    {
        if(s=='-')f=-f;
        s=getchar();
    }
    while(s>47&&s<58)
    {
        x=(x<<3)+(x<<1)+s-48;
        s=getchar();
    }
    return x*f;
}
constexpr int N=1e6+1;
int n,m;
vector<int> g[N];
int in[N];
set<pair<int,int>> s;
int main()
{
    int i,x,y;
    n=read();
    m=read();
    while(m--)
    {
        x=read();
        y=read();
        g[x].push_back(y);
        g[y].push_back(x);
        ++in[x];
        ++in[y];
    }
    for(i=1;i<=n;++i)s.insert({in[i],i});
    while(!s.empty())
    {
        auto u=s.begin();
        s.erase(u);
        x=u->second;
        for(auto v:g[x])
        {
            if(in[v]>in[x])
            {
                s.erase({in[v],v});
                s.insert({--in[v],v});
            }
        }
    }
    for(i=1;i<=n;++i)printf("%d ",in[i]);
    return 0;
}