故事
高桥市正计划修复破旧的道路。 城市的道路网络可以表示为一个平面无向图,以交叉点为顶点,交叉点之间的道路为边。 由于正在维修的道路已封闭,市民必须绕道到达目的地,造成困扰。 考虑到每天可以修复的最大边缘数量以及完成所有修复的最大天数,请计划好哪一天修复哪些边缘,以尽可能减少造成的挫败感。
问题陈述
给定一个边加权无向平面图 N 顶点,我们希望在每个边上执行一次修复工作 D 天。 我们可以在一天内完成每个边缘的修复工作,最多 K 边缘可在当天同时修复。
未进行修复工作的边缘可以在两个方向上通过,并且边缘的权重表示在该边缘上移动所需的距离。 让 d(i,j) 是距顶点的最短距离 i 到顶点 原始图中的 j 。 让 图中的 d_k(i,j) 是距顶点的最短距离 i 到顶点 原始图中的 j 是删除当天要修复的边得到的 k 来自原始图表。 如果 无法从以下位置访问 j 无法从以下位置到达 i,我们定义 d_k(i,j)=10^9。 挫折程度 f_k 当天的维修工作 k 定义为两个不同顶点之间的最短距离的预期增加,如下所示。 \[ f_k = \frac{\sum_{i\neq j}(d_k(i,j)-d(i,j))}{N(N-1)} \]
使用每天的挫败程度的平均值,整个维修工作的挫败程度定义为 \[ \mathrm{round}\left(10^3\times \frac{1}{D}\sum_{k=1}^D f_k\right) \] 找到一个尽可能减少挫败感的维修计划。
评分
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的挫败感级别,MIN 是在该测试用例中获得的所有竞争对手中最低的挫败感级别。提交的分数是相对分数的总和。
最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:2000年。我们将发布 种子.txt (sha256=0522b6c3da4e413908209488368988ebce3b3809c0d9278dc9adaf804896fa23) 比赛结束后。
关于相关评价体系
在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的挫败程度的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出:
N M D K u_1 v_1 w_1 \vdots u_M v_M w_M x_1 y_1 \vdots x_N y_N
- N, M, D,和 K 是整数,分别表示顶点数、边数、最大天数和每天可以修复的最大边数。这些满足 500\leq N\leq 1000, 500\leq M\leq 3000, 5\leq D\leq 30,和 \mathrm{ceil}(M/D)< K\leq 2\cdot\mathrm{ceil}(M/D).
- u_i, v_i,和 w_i 是满足以下条件的整数 1\leq u_i<v_i\leq N 和 1\leq w_i\leq 10^6,并表明 i第一条边连接顶点 u_i 和 v_i 有重量 w_i。每个顶点的度数保证至少为 2。
- (x_i, y_i) 代表坐标 i-第一个顶点,它们是满足的整数 0\leq x_i,y_i\leq 1000。它们用于生成和可视化图表,如果不需要它们,您可以跳过阅读它们。
- 保证给定的图是一个 2 边已连接 平面图使得如果顶点 i 放置在坐标处 (x_i, y_i) 并且边被绘制为连接端点的线段,每对边除了端点之外没有公共点。
输出
让 r_i (1\leq r_i\leq D) 是 i第边缘将被修复。 然后,按以下格式输出到标准输出。
r_1 r_2 \cdots r_M
输入生成
图表的生成
顶点数 N 是由生成的 N=\mathrm{rand}(500,1000)。 随机选择 N 点 (x_1,y_1),\cdots,(x_N,y_N) 从以圆心包含的格点 (500,500) 和半径 500。 如果之间的欧几里得距离 (x_i,y_i) 和已选择的点 (x_j,y_j) (j<i) 小于或等于 10,我们选择 再次 (x_i,y_i) 。 平面图 (V,E) 将这些点作为顶点集 V 的构造如下。
首先,计算 Delaunay 三角剖分 并设置 E 作为三角测量的边集。 生成随机实数值 p 之间 0 和 0.75。 对于每条边 e\in E 按照随机顺序,执行以下操作:删除 e 来自 E 有概率 p 如果两个端点的度数至少为 4。 完成所有边的处理后,如果图 (V,E) 不是2边相连,那么我们恢复 E 我们重做生成过程 p。 每条边的权重 (u,v) 由下式确定 \mathrm{round}(10^3\times \sqrt{(x_u-x_v)^2+(y_u-y_v)^2}).
D 和 K 的生成
D 是由生成的 \mathrm{rand}(5, 30)。 让 K'=\mathrm{ceil}(M/D). K 是由生成的 \mathrm{rand}(K'+1,2K').
工具(输入生成器和可视化工具)
- 网页版:推荐使用 Chrome。 Firefox 将不会显示分数。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。