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