← 返回题目列表

AtCoder · future_contest_2020_final_a

A. 千棵树

中文机器翻译题面 查看原题

問題文

在二维坐标平面上 N 有 1, \ldots, N 个顶点。 此外,S 个无向树 T_1, \ldots, T_S 被给出。

你的任务是,在平面上连接顶点的边, N 构建顶点的无向图, G 并从中G “取出” S 个图。取出的图是 T_1, \ldots, T_S 越“相似”,得分越高。以下将详细说明各项内容。

  • 关于平面上的顶点:顶点 i (1 \leqq i \leqq N) 的坐标为 (x_i, y_i) ,这些坐标都是不超过 0 以上 1000 的整数。此外,每个顶点都有一个正整数值 力量 ,顶点 i 的力量为 c_i 。

  • 木 T_1, \ldots, T_S 关于:都是,1, \ldots, K 号的编号的带有 K 个顶点的无向树。为方便起见,这些树作为编号为 1 的顶点为根的有根树输入,并且在树 T_i (1 \leqq i \leqq S) 中,编号为 j (2 \leqq j \leqq K) 的顶点的父节点是编号为 p_{i,j} 的顶点。关于

  • 边的添加:创建的图 G 可以添加任意数量但不超过 0 本以上 100000 条的无向边。但是,要添加边 \{i, j\} (i \neq j) ,顶点 i, j 之间的欧几里得距离必须不超过 c_i + c_j 。此外,不得产生自环或重边。

  • 关于图的提取:对于每一棵树 T_i (1 \leqq i \leqq S) ,G 的不同 K 頂点 V_{i,1}, \ldots, V_{i,K} 请指定。这表示,对于每个 j (1 \leqq j \leqq K) ,将顶点 V_{i,j} 对应到 T_i 的编号 j 的顶点。同一个顶点也可以用于多棵树。

  • 关于得分:对于每一棵树 T_i (1 \leqq i \leqq S) 关于以下内容来计算分数,S 棵树的分数总和就是该测试用例中的你的得分。

    • 某个整数 x, y (1 \leqq x, y \leqq K) 存在,T_i 拥有边 \{x, y\} 但 不拥有 G 拥有边 \{V_{i,x}, V_{i,y}\} 时: 0 点

    • 否则,整数组合 (x, y) (1 \leqq x, y \leqq K) 并且G 拥有边 \{V_{i,x}, V_{i,y}\} 但 不拥有 T_i 拥有边 \{x, y\} 不拥有的数量为 e_i 。

      • e_i = 0 的时候: 100 点
      • e_i = 1 的时候: 10 点
      • e_i = 2 的时候: 1 点
      • e_i \geqq 3 的时候: 0 点

制約

  • N = 1000
  • S = 1000
  • K = 20
  • 0 \leqq x_i, y_i \leqq 1000
  • 1 \leqq c_i \leqq 1500
  • 1 \leqq p_{i,j} \leqq j-1
  • 输入中的所有值都是整数。

入力

输入将以以下格式从标准输入给出。

N S K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
p_{1,2} p_{1,3} \ldots p_{1,K}
p_{2,2} p_{2,3} \ldots p_{2,K}
:
p_{S,2} p_{S,3} \ldots p_{S,K}

出力

以以下格式输出。

M
A_1 B_1
A_2 B_2
:
A_M B_M
V_{1,1} V_{1,2} \ldots V_{1,K}
V_{2,1} V_{2,2} \ldots V_{2,K}
:
V_{S,1} V_{S,2} \ldots V_{S,K}

这表示所构造的图 G 有 M (0 \leqq M \leqq 100000) 条边。 \{A_1, B_1\}, \{A_2, B_2\}, \ldots, \{A_M, B_M\} (1 \leqq A_i, B_i \leqq N) 边的输出顺序可以是任意的,每条边的端点输出顺序也可以是任意的。V_{i,j} (1 \leqq V_{i,j} \leqq N) 关于...请参照题目正文。

测试用例有 50 个。对于每个测试用例,按照题目正文中所述计算得分,所有测试用例的得分总和即为该提交的得分。

违反上述格式的输出,或有其他任何缺陷(例如:存在自环或多重边,单次取出中顶点重复)的输出,可能会被判定为“错误”。在这种情况下,如果该测试用例作为输入例被提供,则该测试用例的得分为 0 分。对于其他测试用例,则输入例以外的所有测试用例的得分为 0 分。

测试用例生成方法

  • 各頂点 i (1 \leqq i \leqq N) 的坐标 x_i, y_i 分别从 0 以上 1000 以下的整数中均匀随机选择。这些 2N 个坐标都是独立选择的,即使多个点重合,也不会进行重抽。

  • 各頂点 i (1 \leqq i \leqq N) 以5% 的概率为 強頂点、30% 的概率为 中頂点、65% 的概率为 弱頂点 。基于此,c_i 从以下范围的整数中均匀随机选择。对于

    • 強頂点: 500 以上 1500 以下
    • 中頂点: 200 以上 500 以下
    • 弱頂点: 1 以上 200 以下
  • 各 i, j (1 \leqq i \leqq S, 2 \leqq j \leqq K) ,树 T_i 的编号 j 的顶点的父节点 p_{i,j} 从 1 以上 j - 1 以下的整数中均匀随机选择。

入出力例

输入例及输出例可以通过 这个链接 下载。