P2458 [SDOI2006]保安站岗

    • 221通过
    • 709提交
  • 题目提供者 哆啦A梦
  • 评测方式 云端评测
  • 标签 各省省选 2006 山东
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    五一来临,某地下超市为了便于疏通和指挥密集的人员和车辆,以免造成超市内的混乱和拥挤,准备临时从外单位调用部分保安来维持交通秩序。

    已知整个地下超市的所有通道呈一棵树的形状;某些通道之间可以互相望见。总经理要求所有通道的每个端点(树的顶点)都要有人全天候看守,在不同的通道端点安排保安所需的费用不同。

    一个保安一旦站在某个通道的其中一个端点,那么他除了能看守住他所站的那个端点,也能看到这个通道的另一个端点,所以一个保安可能同时能看守住多个端点(树的结点),因此没有必要在每个通道的端点都安排保安。

    编程任务:

    请你帮助超市经理策划安排,在能看守全部通道端点的前提下,使得花费的经费最少。

    输入输出格式

    输入格式:

    第1行 n,表示树中结点的数目。

    第2行至第n+1行,每行描述每个通道端点的信息,依次为:该结点标号i(0<i<=n),在该结点安置保安所需的经费k(<=10000),该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。

    对于一个n(0 < n <= 1500)个结点的树,结点标号在1到n之间,且标号不重复。

    输出格式:

    最少的经费。

    如右图的输入数据示例

    输出数据示例:

    输入输出样例

    输入样例#1: 复制
    6
    1 30 3 2 3 4
    2 16 2 5 6
    3 5 0
    4 4 0
    5 11 0
    6 5 0
    输出样例#1: 复制
    25

    说明

    样例说明:在结点2,3,4安置3个保安能看守所有的6个结点,需要的经费最小:25

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。