华师一附中OI组

标题: Byte大陆( byteland) [打印本页]

作者: admin 时间: 2021-10-15 21:39
标题: Byte大陆( byteland)

【题目描述】

Byte大陆上的王国由一些城市组成，还有一些公路，公路是双向通行的。在某些城市中有堡垒(共有C个)，是国王的部队住所。

当一个城市受到攻击时，国王的军队就会从最近的堡垒从公路上赶来。狡猾的敌人每次会向距离最近的堡垒最远的城市攻击，这让国王大为烦恼。国王打算投资新增加K个堡垒，请你设计一个方案，在某些城市修建新堡垒，使得敌人攻击时，军队能最快到达，即受攻击的城市与最近的堡垒的距离尽可能小，并计算出这个最小距离值。

城市和道路的设计比较独特（见输入说明），N个城市有N个道路，甚至有连接自己城市的道路（参见样例2）。数据保证可以有设计方案，使得每个城市都可以通过公路连接到一个堡垒或它自身就有堡垒。

【输入格式】

第一行，三个整数 N K C。表示有N个城市，标号从0到N-1。新增加K个堡垒；已经在C个城市有堡垒。

第二行，N个整数，第i个整数road(i)表示:第i条公路是连接i城市和road(i)城市的。

第三行，N个整数，第i个整数distance(i)表示:第i条公路的长度。

第三行，C个不同的整数，第i个整数castle(i)表示:在castle(i)城市有堡垒。

【输出格式】

只一行，一个整数。可能的最小距离。

【输入输出样例】

输入	5 1 0 1 2 3 4 0 1 1 1 1 1	10 3 3 0 2 0 0 2 2 8 3 8 7 10 9 1 8 1 3 7 2 8 1 3 4 6
输出	2	3

【数据范围】

30%数据 2 <= N <= 5

50%数据 2 <= N<= 20

100%数据2 <= N <= 50

1<= K <= N

0<= C <= N-K

1<=公路长度 <=10^6

作者: admin 时间: 2021-10-15 21:56
首先二分答案，对于这个答案，我们设法求出这些带环树的最少需要设的城堡数。
我们先考虑没有环的情况，对于一棵树，从叶子结点开始做，记录该节点以下的一棵子树需要多长距离以内要有一座城堡need以及该子树中的城堡可以提供给外面多长距离以内的影响offer。我们贪心地认为，城堡要尽量建在靠上层的位置，下面的能不建就先不建。
1、如果当前子树的offer可以满足当前子树的need，那么当前子树就不存在need了。 2、如果当前子树的need加上与父亲连边的那条权值已经超过了当前二分出来的答案，那么当前节点必须设城堡。
3、用当前子树的need和offer去更新父亲结点的need和offer。
这样一直贪心上去就能得到最少的城堡数。

现在在一棵树上加一个环，我们可以证明这个环上至少有一条边是不需要用到的。假设是由环上的某个点（其可能连向某个城堡）出发从而达到环上的其他点，显然不是环上的每条边都要用一边的，因为不可能更新别人的点，后来反而还更新了自己。
然而我们不知道到底是哪条边不用的时候最优，因此我们需要枚举删掉环上的哪条边，破环成树，然后就按照上面的方法即可。

作者: admin 时间: 2021-10-16 16:28

| 测试点编号 | $\max a_i$  |  $q$ |
| :--------: | :---------: | :----: |
|  $1\sim2$  |  $\leq 10$  |  $2$ |
|  $3\sim4$  | $\leq 10^4$ |  $1$ |
|  $5\sim6$  | $\leq 10^7$ |  $1$ |
| $7\sim 8$  | $\leq 10^3$ | $10^3$ |
| $9\sim10$  | $\leq 10^5$ | $10^3$ |
| $11\sim12$ | $\leq 10^7$ | $10^3$ |
| $13\sim14$ | $\leq 10^5$ | $10^5$ |
| $15\sim16$ | $\leq 10^7$ | $10^5$ |
| $17\sim18$ | $\leq 10^5$ | $10^7$ |
| $19\sim20$ | $\leq 10^7$ | $10^7$ |

欢迎光临华师一附中OI组 (http://hsyit.cn/)