P3651 展翅翱翔之时 (はばたきのとき)

    • 63通过
    • 379提交
  • 题目提供者 lin_toto 站长团
  • 评测方式 云端评测
  • 标签 枚举,暴力 环套树 贪心
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    船が往くよミライへ旅立とう

    船只启航 朝未来展开旅途

    青い空笑ってる(なにがしたい?)

    湛蓝天空露出微笑(想做些什么?)

    ヒカリになろうミライを照らしたい

    化作光芒吧 想就此照亮未来

    輝きは心からあふれ出してもっと先の景色望むんだ

    光辉自内心满溢而出 愿能望见更加前方的景色

    Ah!やっと手にしたミライチケットかざして…!

    Ah!挥舞起终于得手的未来门票…!

    我们Aqours,终于闪闪发亮了!

    2月25和26日,将是我们登上横滨ARENA演唱的日子!

    而且,还要在全日本、甚至全世界的好多影院进行转播呢!

    转播好像还是通过中继卫星传输的呢!

    未来ずら!

    题目描述

    不过,好像中继卫星上,出了一些问题呢……

    我们的中继卫星一共有N颗,编号成1到N。不过,好像一个中继卫星可以且仅可以单向地从另一颗中继卫星那儿接收数据。

    第i颗卫星现在已经被设定到了从第Ai颗卫星 (称为接收源) 那儿接受数据。

    不过这些中继卫星的接收源是可以修改的,只不过每次修改要花一定的资金呢。

    听说要达成中继的话,这些卫星之间必须两两之间能够互相(直接或间接)通信才行啊。

    虽然鞠莉家里很有钱,可是这么大的花费,也得提前准备一下呢。

    所以,你能帮我们算算这样子一共最少要花多少钱吗?

    输入输出格式

    输入格式:

    第一行1个整数N。

    接下来N行,每行2个整数Ai,Ci,表示初始时,第i个中继卫星从第Ai颗卫星处接收数据,以及该卫星调整接收源的所需花费。

    输出格式:

    输出一个整数,表示鞠莉所需准备的最小的花费。

    输入输出样例

    输入样例#1: 复制
    4
    2 2
    1 6
    1 3
    3 1
    输出样例#1: 复制
    5

    说明

    10% N<=10
    40% N<=15
    70% N<=3000
    100% 2<=N<=100000, 1<=Ci<=10^9

    以下是彩蛋

    事实上LoveLive的直播卫星中继只有一颗星,而且永远都是不加密的。

    导致只要有一个卫星锅就可以在家偷偷看直播,也就是传说中的卫星源。

    lin_toto: 万代南梦宫都把浅水湾给买了,居然只有回放,只好跑到香港the sky去看+手动滑稽。

    至于为什么看转播,eplus表示LoveLive系列演唱会的票大家尽管抽选尽管抢,买得到算我输。

    于是lin_toto在去年μ's Final LoveLive的时候拿肉鸡把eplus搞趴下了,然后就买到了。

    于是今年eplus连抢票都不让抢了,全抽选,抽得到算我输。

    然后lin_toto就去看转播了。

    标程展开

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