自动搬运

查看原文

来自洛谷，原作者为

	mairuisheng 1.广州市第六中学 2.每周五回关

搬运于2025-08-24 23:12:22，当前版本为作者最后更新于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;
}