首页
题库
训练
比赛
作业
讨论
排名
登录
Language
English
한국어
简体中文
正體中文
1 条题解
0
DHEnry
SU
@
2026-11-15 21:43:59
题目分析
题解
首先注意到题目本质是最小化删除时的最大代价,非常典型的最小化最大值,自然想到要用 二分答案。
我们二分最大允许代价
mid
,然后做一次
check(mid)
来判断当前答案是否合法。
check(mid)
的核心:可以用 BFS(类似拓扑排序)维护一个可删点的队列(代价小于 mid),出队就更新其他相邻点代价,如果相邻的代价小于 mid 且没有入队过,就加入队列。
最后如果所有点都能在 BFS 中被访问到,就说明当前
mid
可行。
时间复杂度:
O
(
(
N
+
M
)
log
S
)
O((N+M) \log S)
O
((
N
+
M
)
lo
g
S
)
(S 为点权和的范围)
1
小明的清理行动
查看题目
登录后递交
讨论
题解
文件
统计
信息
ID
209
时间
1000ms
内存
512MiB
难度
3
标签
模拟
梦熊联盟
梦熊二十连测
2025
递交数
1
已通过
1
上传者
DHEnry
关闭
登录
使用您的 Hydro 通用账户
使用 FMCRAFT 登录
忘记密码或者用户名?