「KDOI-02」一个截的拦
题目背景
「{!@@(*@@¥';l]dw@)%)%&^_^}(可恶的人类!我一定会回来的!)」
它将飞船拉到了最高速度,试图离开这个充满人类的地狱。
……
题目描述
过了那么多年,外星人的飞船速度早已比不过地球的飞船。因此,它决定使用折跃点逃离。
平面地图上有 $n$ 个折跃点,坐标分别为 $(x_i,y_i)$。某些折跃点之间有双向空间隧道连接,共 $m$ 条隧道,每条隧道分别连接折跃点 $u_i,v_i$,且激活该隧道需要消耗 $w_i$ 单位能量。**请注意,为了保证空间隧道之间互不干扰,对于任意两条空间隧道 $\bm{i,j}$,都保证连接点 $\bm{u_i,v_i}$ 与点 $\bm{u_j,v_j}$ 的线段没有交点。保证不存在起点和终点都相同的两条空间隧道。**
外星人的科技非常神奇,因此为了成功折跃离开,外星人必须经过地图上的所有折跃点 **至少一次**,它可以从任意一点开始折跃并从任意一点结束折跃,最终,外星人所花费的总能量为激活路径上所有隧道所消耗能量的 **按位或运算和**。经过两次或两次以上同一隧道只需激活一次该隧道。
外星人的飞船上拥有 $x$ 单位能量,因此,它所选择的折跃方案花费的总能量不能超过 $x$。为了拦截外星人,地方可以执行以下操作任意多次:
+ 选择一条连接 $u$ 和 $v$ 的双向隧道(你需要保证在点 $u$ 和 $v$ 之间存在双向隧道连接);
+ 将激活它所需要的能量增加 $w$($w\ge0$ 且操作后激活该通道所需要的能量不能超过 $2^{31}-1$)。
其中,$u,v,w$ 都可以自行指定。**每次操作所需要的代价为 $w$ 的二进制表示下 $1$ 的个数。**(即 `c++` 中的 `__builtin_popcount()` 函数)
为了赎罪,你需要设计一种操作方案,使得外星人无法通过折跃逃离,并最小化该方案所需要的代价。
输入输出格式
输入格式
从标准输入读入数据。
输入的第一行包含 $1$ 个正整数 $W$,表示该测试点的评分参数。
输入的第二行包含 $3$ 个整数 $n,m,x$,分别表示折跃点个数,双向隧道条数以及外星人飞船上拥有的能量。
第 $3$ 至 $(n+2)$ 行,第 $(i+2)$ 行有 $2$ 个整数 $x_i,y_i$,表示第 $i$ 个折跃点的坐标。
接下来 $m$ 行,每行 $3$ 个整数 $u_i,v_i,w_i$,表示每条双向隧道连接的两个折跃点和激活所需能量。
输出格式
输出到标准输出。
**本题采用自定义校验器(special judge)评测。**
输出的第一行应包含一个非负整数 $k$,表示操作总次数。
接下来 $k$ 行,每行一次操作,形如 $u~v~w$,表示将激活连接 $u$ 和 $v$ 的双向隧道所需能量增加 $w$。
你需要保证 $0\le k\le 10000$,否则将被判定为不合法答案。
输入输出样例
输入样例 #1
1
5 6 9
0 1
0 0
0 -1
-1 0
1 0
1 2 10
1 4 1
2 3 8
3 4 5
3 5 1
1 5 1
输出样例 #1
1
2 3 2
输入样例 #2
见附件中的 intercept2.in
输出样例 #2
见附件中的 intercept2.ans
输入样例 #3
见附件中的 intercept3.in
输出样例 #3
见附件中的 intercept3.ans
说明
**【样例解释】**
+ **样例 1 解释:**
经过操作后的平面地图如下图所示(省略坐标轴):
![](https://cdn.luogu.com.cn/upload/image_hosting/cbg7sir6.png)
由于与 $2$ 号折跃点相连的空间隧道所需要的激活能量全部为 $10$,所以成功折跃所需要的能量至少为 $10$,因此外星人无法通过折跃逃离,代价为 $1$,显然不存在代价更小的操作方案。
***
**【评分方式】**
对于每个测试点,如果你的操作方案不合法或使得外星人能够成功通过折跃逃离,你将在该测试点得到 $0$ 分。
否则,设该测试点的评分参数为 $W$,标准答案的代价为 $a$,你的操作方案的代价为 $b$,则你的分数 $s$ 将由下列公式给出:
$$
s=\max\left(1-\frac{b-a}{a}\times W,0\right)\times10
$$
***
**【数据范围】**
对于 $100\%$ 的数据,$12\le n\le 53280$,$n-1\le m\le 3n-6$,$0\le x<2^{31}-1$,$0\le|x_i|,|y_i|\le3\times10^4$,$0\le w_i<2^{31}$,$1\le W\le 1000$。
|测试点编号|$n=$|$m=$|$W=$|数据随机生成|
|:--:|:--:|:--:|:--:|:--:|
|$1$|$12$|$26$|$1000$|否|
|$2$|$12$|$26$|$1$|是|
|$3$|$200$|$579$|$2$|是|
|$4$|$500$|$1482$|$5$|是|
|$5$|$5000$|$14971$|$5$|否|
|$6$|$5000$|$14962$|$1$|是|
|$7$|$10656$|$30188$|$1000$|否|
|$8$|$10656$|$30188$|$5$|否|
|$9$|$53280$|$150960$|$1000$|否|
|$10$|$53280$|$150960$|$1000$|否|
***
**【校验器】**
为了方便测试,在 $\texttt{intercept}$ 目录下我们下发了 $\texttt{checker.cpp}$ 文件。你可以编译该文件,并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致,你不需要也不应该关心其代码的具体内容。
编译命令为:
```plain
g++ checker.cpp -o checker -std=c++14
```
使用方式为:
```
./checker <inputfile> <outputfile> <answerfile>
```
校验器可能会返回以下状态中的其中一种:
+ $\texttt{accepted}$:表示你的输出完全正确。
+ $\texttt{points } x$:表示你的输出部分正确,可以在该测试点得到比例为 $x$ 的分数。
+ $\texttt{wrong answer}$:表示你在该测试点得到 $0$ 分。
对于所有非 $\texttt{accepted}$ 状态,校验器接下来会输出以下信息中的一种:
+ $\texttt{A}$:表示你的输出不合法。
+ $\texttt{B x y}$:表示你的输出方案的代价为 $x$,标准答案为 $y$。
+ $\texttt{C}$:表示你的输出方案使得外星人能够成功通过折跃逃离。
***
**【后记】**
他知道,他将永远离开家乡了。他仍记得,在倒转时空前,指挥官最后的那句叮嘱。他花了几乎半辈子,终于建立了新的基地,重整了军队。他的目的,就是为了防止这一切重蹈覆辙。现在,基地被毁了,他被困在这暗淡无光的星系里。他终于醒悟了,一切都是早已被决定好的。
「指挥官,对不起。」
「舱室将在十秒后自毁。十。九。八。七……」
举起手枪,对准自己太阳穴。
「六。五。四。三……」
随着砰的一声,他无力地倒下了,眼里黯淡无光。
「二。一。」
巨响过后,无人将被铭记。