← 返回题目列表

AtCoder · hitachi2017_1_a

A. 问题1

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

问题

下面假设我们有两张图。 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。