1 条题解

  • 0
    @ 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)​ (S 为点权和的范围)
    • 1

    信息

    ID
    209
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者