/ Vijos / 题库 / 家访 /

题解

1 条题解

  • 0
    @ 2020-01-02 19:39:43

    正解=最小生成树

    显然拆完路后,这是一棵树,

    题目要求访问所有点,

    不难发现,除根节点外,每一个点的访问次数=该点的度

    每给当前生成树一条边,则该边连接的两点都会增加一个度

    因此一条边的实际权值 = 边长+该边所连两点的点权

    然后用Kruskal做最小生成树即可

    根结点的反问次数会多一,所以直接找个点权最小的点做根节点即可

  • 1

信息

ID
1678
难度
9
分类
贪心 | 树结构 | 生成树图结构 | 并查集 点击显示
标签
递交数
1
已通过
1
通过率
100%
被复制
2
上传者