P3125 [USACO15OPEN]Bessie的生日自助餐Bessie's…

    • 136通过
    • 299提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2015 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    For Bessie the cow’s birthday, Farmer John has given her free reign over one

    of his best fields to eat grass.

    The field is covered in $N$ patches of grass ($1 \le N \le 1000$), conveniently

    numbered $1\ldots N$, that each have a distinct quality value. If Bessie eats

    grass of quality $Q$, she gains $Q$ units of energy. Each patch is connected to

    up to 10 neighboring patches via bi-directional paths, and it takes Bessie $E$

    units of energy to move between adjacent patches ($1 \le E \le 1,000,000$).

    Bessie can choose to start grazing in any patch she wishes, and she wants to

    stop grazing once she has accumulated a maximum amount of energy.

    Unfortunately, Bessie is a picky bovine, and once she eats grass of a certain

    quality, she’ll never eat grass at or below that quality level again! She is

    still happy to walk through patches without eating their grass; in fact, she

    might find it beneficial to walk through a patch of high-quality grass without

    eating it, only to return later for a tasty snack.

    Please help determine the maximum amount of energy Bessie can accumulate.

    为了庆祝奶牛Bessie的生日,Farmer John给了她一块最好的牧场,让她自由的享用。

    牧场上一共有N块草地(1≤N≤1000),编号为1...N,每块草地上牧草的质量都不同。

    如果Bessie吃掉的草地上牧草质量为Q,她可以获得Q单位的能量。

    每块草地最多和10块草地有相连的道路,在相连的两个草地之间走动需要消耗E单位的能量(1≤E≤1,000,000)。

    Bessie可以从任意一块草地开始吃草,并且想要在获得了最多能量的时候停止。

    有点遗憾的,Bessie是一头挑食的奶牛,一旦她吃过了一定质量的牧草,她就不会再吃相同或更低质量的牧草!但是她仍然很愿意路过某些草地,而不吃它们。实际上,她发现路过一块高质量的草地而不吃它,等一下返回再去享用,有时会更有利!

    请帮忙计算Bessie能够获得的能量的最大值。

    输入输出格式

    输入格式:

    The first line of input contains $N$ and $E$. Each of the remaining $N$ lines

    describe a patch of grass. They contain two integers $Q$ and $D$ giving the

    quality of the patch (in the range $1\ldots 1,000,000$) and its number of

    neighbors. The remaining $D$ numbers on the line specify the neighbors.

    1行:包含两个整数N和E。

    接下来N行:每行描述一块草地,首先两个整数Q和D,分别表示草地上牧草的质量(范围1…1,000,000)和相连的草地数量。然后D个整数表示相连的草地。

    输出格式:

    Please output the maximum amount of energy Bessie can accumulate.

    输出Bessie能够获得的能量的最大值。

    输入输出样例

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

    说明

    Bessie starts at patch 4 gaining 5 units of energy from the grass there. She

    then takes the path to patch 5 losing 2 units of energy during her travel.

    She refuses to eat the lower quality grass at patch 5 and travels to patch 3

    again losing 2 units of energy. Finally she eats the grass at patch 3 gaining 6 units of energy

    for a total of 7 energy.

    Note tha the sample case above is different from test case 1 when you submit.

    感谢@蒟蒻orz神犇 提供翻译

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