Bessie's Birthday Buffet

题目描述

为了给奶牛 Bessie 过生日，农夫 John 让她可以在他最好的一块田地里自由吃草。\n这块田地上有 $N$ 块草地斑块（$1 \le N \le 1000$），方便起见编号为 $1\ldots N$，且每块斑块都有一个互不相同的品质值。若 Bessie 吃下品质为 $Q$ 的草，她将获得 $Q$ 单位能量。每块斑块通过双向路径与至多 10 个相邻斑块相连，在相邻斑块间移动需要消耗 $E$ 单位能量（$1 \le E \le 1,000,000$）。\nBessie 可以选择从任意斑块开始吃草，她希望在能量累积达到最大时停止。\n不幸的是，Bessie 很挑剔：一旦她吃过某个品质的草，她将永远不会再吃品质小于或等于该品质的草！她仍然愿意穿过斑块而不吃那里的草；事实上，她甚至可能先走过一块高品质草地而不吃，之后再回来享用美味点心。\n请帮助确定 Bessie 能累积到的最大能量。

输入格式

第一行输入包含 $N$ 和 $E$。接下来的 $N$ 行描述各个草地斑块。每行包含两个整数 $Q$ 和 $D$，分别表示该斑块的品质（范围为 $1\ldots 1,000,000$）以及它的邻居数量。该行剩余的 $D$ 个数字给出这些邻居的编号。

输出格式

请输出 Bessie 能累积到的最大能量。

5 2\n4 1 2\n1 3 1 3 4\n6 2 2 5\n5 2 2 5\n2 2 3 4

7

提示

Bessie 从斑块 4 开始，吃掉那里的草获得 5 单位能量。然后她走到斑块 5，在路上消耗 2 单位能量。她拒绝吃斑块 5 上品质更低的草，并前往斑块 3，再次消耗 2 单位能量。最后她吃掉斑块 3 的草，获得 6 单位能量，总计为 7。\n注意：上面的样例与提交时的测试点 1 不同。\n[题目来源：Austin Anderson 和 Brian Dean, 2015]

标签: USACO|2015|Silver

来源

USACO|2015|Silver