问题
下面假设我们有两张图。 G=(V,E) 由一组顶点组成 V 和边缘 E 应分配权重。第二张图 G_{emb}=(V_{emb},E_{emb}) 也由一组顶点组成 V_{emb} 和边缘 E_{emb} 并且应为正方形 国王图,顶点标签如下图所示。在我们下面解释的约束下,将每个顶点分配给 V 正好到一个顶点 V_{emb} 使得以下分数变得尽可能高。

分数
对于源代码的给定输出,其中图中的每个顶点 G 恰好分配给图中的一个顶点 G_{emb},输出的分数计算如下:
- 通过将图的每条边的权重相加得到分数 G 连接顶点 u, v,如果图中对应的顶点 G_{emb} 通过边连接。
- 为了评估您的总分,我们将在总共 30 输入图表 G (包括18张随机图和12张完整图)并将相应分数相加。*
- 请注意,任何超出时间或内存限制的算法运行都不会影响您的最终得分。对于任何违反下面指定的输出格式的输出也是如此。
* 与我们最初的公告相反,我们更改了评估您的最终得分和排名(如积分榜上所列)的规则。特别是,在第一场比赛期间,您的分数将根据上面公布的当前 30 个测试用例进行估算。这将允许估计您的排名,如部分排名中列出的那样。然而,比赛结束后,您的最终分数和排名将通过在 150 个先前未公开的输入图表上运行您的最终提交内容来确定。在这 150 个测试用例中,90 个是随机图(包括 40 个最大度数为 8 的随机图),60 个是完整图。请注意,这意味着比赛结束后最终排名可能会发生变化。最终分数评估的这一变化是与 AtCoder Inc. 达成一致的决定,并且有必要惩罚针对当前 30 个测试图的过度代码调整。
输入
通过标准输入以以下格式给出输入。所有输入都有整数值。
|V| |E|
u_1 v_1 w_1
u_2 v_2 w_2
:
u_{|E|} v_{|E|} w_{|E|}
|V_{emb}| |E_{emb}|
a_1 b_1
a_2 b_2
:
a_{|E_{emb}|} b_{|E_{emb}|}
- |V| 和 |E| 表示图的顶点和边的总数 G。
- 该行 u_i, v_i, w_i 表示顶点 u_i 和顶点 图表的 v_i 图表的 G 由权重边缘连接 w_i.
- |V_{emb}| 和 |E_{emb}| 表示图的顶点和边的总数 G_{emb}。
- 该行 a_i, b_i 表示顶点 a_i 和顶点 图表的 b_i 图表的 G_{emb} 通过边连接。
图的约束 G
- 2 \leq |V| \leq 5 \times 10^2
- 1 \leq |E| \leq min(|V|(|V|-1)/2, \ \ 2 \times 10^4)
- 1 \leq u_i \lt v_i \leq |V|
- 0 \leq w_i \leq 15
- If i \neq j , u_i \neq u_j or v_i \neq v_j.
- 图表 G 已连接。
图的约束 G_{emb}
- G_{emb} 是方形国王图。
- 4 \leq |V_{emb}| \leq 3.6 \times 10^3 和 |V_{emb}| 是一个平方数。
- |V| \leq |V_{emb}|
- 1 \leq a_i \lt b_i \leq |V_{emb}|
输出
输出应采用以下格式,并应通过标准输出进行处理。
s_1 t_1
s_2 t_2
:
s_{|V|} t_{|V|}
- 该行 s_i, t_i 表示顶点 s_i 图表的 G 被分配给顶点 t_i 图表的 G_{emb}.
- 图中的所有顶点 G 应分配给图中的顶点 G_{emb} 并且关系应该是一对一的。有关详细信息,请参阅输出约束。
输出约束
- 输出应包括 |V| 行。
- 1 \leq s_i \leq |V|
- 1 \leq t_i \leq |V_{emb}|
- If i \neq j, s_i \neq s_j 和 t_i \neq t_j.
输入图怎么样 G 已生成?
对于所有测试用例,给定的图 G 是随机图或完整图。下面,我们简要解释一下这些图是如何生成的。详细信息请参阅 示例代码.
随机图
- 首先,一棵树 |V| 顶点是随机生成的。随后, |E| - |V| + 1 边随机添加到树中。最后,为每条边分配一个随机值的权重。
- 此外, 8 随机图将有一个额外的约束。他们的最大度数最多为 8。这些图是通过随机添加空边创建的,仅在度数小于的顶点之间 8.
完整图表
- 为每条边分配随机值的权重 1 \leq u \lt v \leq |V|.
输入示例 1
3 3 1 2 1 2 3 2 1 3 4 9 20 1 2 1 4 1 5 2 4 2 3 2 5 2 6 3 5 4 5 4 7 4 8 5 7 5 6 5 8 5 9 6 8 3 6 6 9 7 8 8 9
输出示例 1
1 1 2 2 3 5
此输入示例对应于本问题页面开头的示意图。
为了演示如何对输出进行评分,让我们考虑边缘 (1, 3) 图表的 G 位于输入示例中的第四行。我们现在判断,它的权重值是否 应将 4 添加到分数中。为此,我们考虑输出示例的第一行和第三行。第一行指定顶点 1 图表的 G 被分配给顶点 1 图表的 G_{emb}。第三行指定顶点 图中的 3 图表的 G 被分配给顶点 5 在图中 G_{emb}。最后,我们检查对应的顶点对 (1,5) 是否 G_{emb} 通过边连接。输入文件中的第 8 行证实了这一点。因此,应在总分中加上相应的权重值。
在此输出示例中,图的每个连接的顶点对 G 被分配给图的连接顶点对 G_{emb}。因此,总分是所有权重值的总和 7.
输入示例 2
7 21 1 2 8 1 3 14 1 4 7 1 5 14 1 6 15 1 7 7 2 3 7 2 4 0 2 5 13 2 6 14 2 7 13 3 4 12 3 5 1 3 6 8 3 7 8 4 5 8 4 6 3 4 7 8 5 6 9 5 7 9 6 7 1 64 210 1 2 1 9 1 10 2 9 2 3 2 10 2 11 3 10 3 4 3 11 3 12 4 11 4 5 4 12 4 13 5 12 5 6 5 13 5 14 6 13 6 7 6 14 6 15 7 14 7 8 7 15 7 16 8 15 9 10 9 17 9 18 10 17 10 11 10 18 10 19 11 18 11 12 11 19 11 20 12 19 12 13 12 20 12 21 13 20 13 14 13 21 13 22 14 21 14 15 14 22 14 23 15 22 15 16 15 23 15 24 16 23 17 18 17 25 17 26 18 25 18 19 18 26 18 27 19 26 19 20 19 27 19 28 20 27 20 21 20 28 20 29 21 28 21 22 21 29 21 30 22 29 22 23 22 30 22 31 23 30 23 24 23 31 23 32 24 31 25 26 25 33 25 34 26 33 26 27 26 34 26 35 27 34 27 28 27 35 27 36 28 35 28 29 28 36 28 37 29 36 29 30 29 37 29 38 30 37 30 31 30 38 30 39 31 38 31 32 31 39 31 40 32 39 33 34 33 41 33 42 34 41 34 35 34 42 34 43 35 42 35 36 35 43 35 44 36 43 36 37 36 44 36 45 37 44 37 38 37 45 37 46 38 45 38 39 38 46 38 47 39 46 39 40 39 47 39 48 40 47 41 42 41 49 41 50 42 49 42 43 42 50 42 51 43 50 43 44 43 51 43 52 44 51 44 45 44 52 44 53 45 52 45 46 45 53 45 54 46 53 46 47 46 54 46 55 47 54 47 48 47 55 47 56 48 55 49 50 49 57 49 58 50 57 50 51 50 58 50 59 51 58 51 52 51 59 51 60 52 59 52 53 52 60 52 61 53 60 53 54 53 61 53 62 54 61 54 55 54 62 54 63 55 62 55 56 55 63 55 64 56 63 8 16 16 24 24 32 32 40 40 48 48 56 56 64 57 58 58 59 59 60 60 61 61 62 62 63 63 64
输出示例 2
1 10 2 9 3 17 4 11 5 2 6 1 7 18
该输入示例对应于以下示意图。

发生器、测试仪和参考
可以通过以下方式下载此问题的生成器和测试器 链接。
有关此问题的先前研究,请参阅:
H. Neven 等人,“NIPS 2009 演示:使用量子退火的硬件实现进行二进制分类。”量子(2009):1-17。