#2244. 星际矿业
星际矿业
星际矿业
题目描述
星际矿业 Alice 和 Bob 在玩一款星际开发游戏,游戏中有 个星球,编号为 。星球 上的矿产储量为 。 为了在不同星球间移动,星际公司建造了 个星门,符合如下规则: 星球 各拥有恰好一个星门。具体地,给出 ,通过星球 的星门可以到达星 球 。星门是单向的,不可返回。 从任意一个星球出发,都可以通过星门到达星球 ,那里是星际市场所在地。 Bob 拥有 艘采矿船,他可以把这些采矿船分别投放到 个星球上,采矿船可以沿着星门移动,并采集 沿途星球的所有矿藏(一个星球可能被多艘采矿船经过,但只能被采集一次),最终来到星球 将所载 矿物全部出售。 然而,在 Bob 开始采矿之前,触发了星门维护事件,星际公司决定更新星门的布局,拆毁 座星门,再 重建 座星门,使得星门的结构仍然符合规则。由于游戏机制, 可以在 中任取,也就是说 星门可能完全没有更新。 在花费了一些外交点数后,拆毁星门的任务被外包给了 Alice,重建星门的任务被外包给了 Bob。在重建 完成后,Bob 投放采矿船进行采矿。 Bob 想让他采集到的矿石总量越大越好,Alice 想让 Bob 采集到的矿石总量越小越好,在此基础上,她 希望能拆毁尽量多的星门。若双方都采取最优策略,求出 Bob 最终的采矿总量,以及在此基础上 Alice 最多拆毁的星门个数。 输入格式 本题有多组测试数据。输入的第一行包含一个正整数 ,表示测试数据组数。 接下来依次是 组测试数据。对于每组测试数据: 输入的第一行为两个正整数 。 第二行为 个正整数 ,表示各个星球上的矿藏储量。 第三行为 个正整数 ,表示初始时星球 的星门所到达的星球。 输出格式 对于每组数据,输出一行两个非负整数,分别表示 Bob 最终的采矿总量,以及在最小化 Bob 采矿量的 基础上 Alice 最多拆毁的星门个数。 样例一 input 3 3 1 1 1 1 1 1 7 2 5 8 8 5 8 2 3 1 2 3 4 1 4 16 4 2 7 9 7 9 5 10 10 2 10 5 2 7 6 9 4 1 1 3 3 1 6 5 8 3 10 2 7 8 9 3 output 2 0 37 2 87 4 explanation 第一组数据中,若 Alice 拆除星球 的星门,Bob 可以重建为 ,这样只需要在星球 上放 置唯一的一辆采矿船,就能采集到三个星球的所有 单位矿藏。Alice 拆除星球 的星门的情况类 似。故 Alice 只好不拆除任何星门,这样可以让 Bob 的最大采矿量为 。 第二组数据中,Alice 的一种符合题意的方案是拆除星球 的星门。 数据范围与约定 设 表示单个测试点中所有测试数据的 的和。对于所有测试点,保证 ; , ; , ; , 。 子任务编号 特殊性质 分值 无 无 无 无 特殊性质 A: 。 特殊性质 B: 或 , 。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
3 1
1 1 1
1 1
7 2
5 8 8 5 8 2 3
1 2 3 4 1 4
16 4
2 7 9 7 9 5 10 10 2 10 5 2 7 6 9 4
1 1 3 3 1 6 5 8 3 10 2 7 8 9 3
2 0
37 2
87 4