1 条题解

  • 0
    @ 2026-11-15 15:17:19

    题目分析

    部分分

    枚举所有点亮灯的顺序即可(适合 nn 很小的数据)。

    正解

    把问题转化为最小生成树:若两点之间的花费高于 mm,就把它改为 mm。

    具体做法是造一个虚点,让虚点连接所有点、边权均为 mm。从虚点连向某个点的操作,就等价于「直接花费 mm 点星光能量点亮这盏灯」。在新图上跑一遍最小生成树(Kruskal 或 Prim),得到的边权和就是答案。

    这样就把「可以任意选择起点」的问题统一处理掉了,不需要额外枚举起始点。

    • 1

    信息

    ID
    110
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者