故事
在 AtCoder 办公室,正在为稍显迟来的圣诞晚会做准备。首席执行官高桥决定砍掉有根的树来用作圣诞树。
有根树中的每个顶点都有一个 颜值,如果美丽的顶点位于高处,聚会场地看起来会更有吸引力。然而,如果有根的树太高,它会撞到 AtCoder 办公室的天花板。因此,可带入场馆的有根树木的高度是有限制的。
你的任务是从给定的图中剪掉几棵有根树,以最大化 吸引力 聚会地点 。
问题陈述
给你一个连通的无向平面图 G 与 N 顶点和 M 边缘。顶点编号从 0 to N-1,边的编号从 0 to M-1。顶点坐标 v 是 (x_v, y_v)和边缘 i 连接顶点 u_i 和 v_i。每个顶点都有一个 颜值,这是一个正整数。的 顶点的 颜值 顶点的 v is A_v.
的 吸引力 聚会地点 一棵有根的树 T 定义如下: 让 高度 h_v 顶点的 v in T 是从根到路径中的边数 有根树的 v。 的 吸引力 聚会地点 a(T) 有根树的 T 定义为 a(T):=\sum_{v \in T} (h_v + 1) A_v.
你的任务是根据给定的图构造一组有根树 G 满足以下条件,并求和 吸引力 聚会地点 尽可能大:
- 每棵有根树中的所有边 T 必须属于 G.
- 中的每个顶点 G 恰好属于一棵有根树。
- 每棵有根树中所有顶点的高度必须小于或等于 H.
评分
让 F 是您构建的有根树的集合。那么,你将获得分数 1+\sum_{T\in F}a(T).
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N M H
A_0 \cdots A_{N-1}
u_0 v_0
\vdots
u_{M-1} v_{M-1}
x_0 y_0
\vdots
x_{N-1} y_{N-1}
输入满足以下约束:
- N = 1000
- 1000 \leq M \leq 3000
- H = 10
- 1 \leq A_v \leq 100
- 0 \leq u_i < v_i \leq N-1
- 0 \leq x_v, y_v \leq 1000
- (x_v, y_v) 都是不同的。
- 所有输入均为整数。
- 给定的图是连通平面图。如果顶点 v 放置在坐标处 (x_v, y_v),并且每条边都被绘制为连接其端点的线段,没有两条边共享除端点之外的点。
输出
让 p_v 是顶点的父级 v 在构造的有根树集中。 如果 v 是一个根,让 p_v=-1。 然后,按以下格式输出到标准输出:
p_0 p_1 \cdots p_{N-1}
您的程序可能会输出多个解决方案。 如果输出多个解,则仅使用最后一个进行评分。 您可以使用可视化工具的网络版本来比较多个解决方案。
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
图表的生成 G
随机选择 N 点 (x_0,y_0),\cdots,(x_{N-1},y_{N-1}) 从以中心为圆心的圆中包含的格点 (500,500) 和半径 500。 如果之间的欧几里得距离 (x_i,y_i) 和已选择的点 (x_j,y_j) (j<i) 小于或等于 15,我们选择 再次 (x_i,y_i) 。
对于顶点集 V 如上所述获得,计算 Delaunay 三角剖分,定义三角剖分的边集为 E,让 G = (V, E).
美丽价值观的产生 A
对于每个顶点 v,颜值 A_v 是使用生成的 \mathrm{rand}(1, 100).
工具(输入生成器、本地测试器和可视化器)
- 网页版:这个比本地版本更强大,可以显示动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。