A - Problem 1 Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MB

問題文

頂点集合V、辺集合EからなるグラフをG=(V,E) とする。二つのグラフ G=(V, E) と G_{emb}=(V_{emb},E_{emb}) が与えられているとし、グラフ G の各辺には重みが定義されているとせよ。入力と出力の箇所で説明する制約のもとで、以下で説明する得点ができるだけ高くなるように、 V のすべての要素に対し V_{emb} の頂点を対応させよ。なお、 G_{emb} は以下の図のような、一行に含まれる頂点数と一列に含まれる頂点数が等しい正方形型の King's Graph である。King's Graph の頂点の番号付けについては、左上が 1 であり、以降左から右に順に番号を振り、行末に到達したときは次の行から同様に順に番号を振るものとする。

得点計算について

各テストケースの得点およびこの問題の得点は、以下のように計算します。

  • G の辺 (u, v) について以下の条件が成り立つときその辺の重みを得点に加算する。条件：G_{emb} において、u と対応する G_{emb} の頂点 p と、v と対応する G_{emb} の頂点 q の間に辺 (p, q) が存在する。
  • テストケースの得点は、G の辺であって上記の条件を満たす辺の重みの総和です。
  • テストケースは全部で 30 個（ランダムグラフが18個、完全グラフが12個）あり、各テストケースの得点の合計がこの問題の得点になります。*
  • 各テストケースについて、実行制限時間又はメモリを超過する、ないしは出力が正しい出力フォーマットに従っていないものは 0 点となります。

*当初のアナウンスと異なり、最終順位・得点はシステムテストにより決定します。本テストはコンテスト終了後、本テストケースとは異なる、150個のジャッジデータで最終提出をリジャッジすることで評価します。150個のジャッジデータは、テストケースと同じ方法で生成し、90個のランダムグラフ（そのうち40個は各頂点の次数が高々8）と60個の完全グラフで構成します。本テストにより、最終順位が変動するかもしれません。本テストはシード値の特定等、チューニングによる高得点を防ぐためのものであり、AtCoder社様との協議の結果、本テストにて最終順位を決定します。

入力

入力は以下の形式で標準入力から与えられます。入力はすべて整数値です。

|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 はグラフ G の辺についての情報であり、頂点 u_i と頂点 v_i が重み w_i の辺で接続されていることを表します。
  • |V_{emb}| と |E_{emb}| はグラフ G_{emb} の頂点の数と辺の数を表します。
  • a_i, b_i はグラフ G_{emb} の辺についての情報であり、頂点 a_i と頂点 b_i が接続されていることを表します。

グラフ 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
  • i \neq j ならば、 u_i \neq u_j または v_i \neq v_j
  • 与えられるグラフは連結である

グラフ G_{emb} についての制約

  • G_{emb} は正方形の King's グラフである
  • 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}|

出力

出力は以下の形式で標準出力に |V| 行で出力してください。

s_1 t_1
s_2 t_2
:
s_{|V|} t_{|V|}
  • s_i, t_i は、グラフ G の頂点 s_i が、グラフ G_{emb} の頂点 t_i と対応していることを表します。
  • グラフ G のすべての頂点に対して対応関係が明らかになっており、かつ G と対応関係にある G_{emb} の頂点について、それに対応する G の頂点は一意に定まらなければいけません。詳しくは、出力についての制約をお読みください。

出力についての制約

  • 出力は |V| 行からなる
  • 1 \leq s_i \leq |V|
  • 1 \leq t_i \leq |V_{emb}|
  • 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| を満たすすべての (u, v) の組について、重み w をランダムに設定し辺を張ります。

入力例 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

この入力例は、問題文冒頭の図で登場したグラフと同一のものです。

G の 3 つめの辺 (1, 3) に着目してみましょう。G の頂点 1 に対応する G_{emb} の頂点 1 と、G の頂点 3 に対応する G_{emb} の頂点 5 を結ぶ辺 (1, 5) が存在するので、この辺の重みである 4 が得点に加算されます。

他のすべての辺も対応する 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, et al., "NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing." Quantum (2009): 1-17.

Problem

In what follows assume we are given two graphs. The first graph G=(V,E) consists of a set of vertices V and edges E to which weights shall be assigned. The second graph G_{emb}=(V_{emb},E_{emb}) also consists of a set of vertices V_{emb} and edges E_{emb} and shall be a square King's Graph, with vertex labels as illustrated in the figure below. Under the constraints that we explain below, assign each vertex in V to exactly one vertex in V_{emb} such that the following score becomes as high as possible.

Score

For a given output of a source code in which each vertex in the graph G is assigned to exactly one vertex in the graph G_{emb}, the score of the output is calculated as follows:

  • The score is obtained by adding the weight of each edge of the graph G connecting the vertices u, v, if the corresponding vertices in the graph G_{emb} are connected by an edge.
  • To evaluate your total score, we will run your algorithm on a total of 30 input graphs G (including 18 random graphs and 12 complete graphs) and add up the corresponding score.*
  • Note that any run of your algorithm which exceeds either the time or the memory limit will not contribute to your final score. The same is true for any output, which violates the output format specified below.

* In contrast to our initial announcement, we have changed the rules by which your final score and rank, as listed in standings, will be evaluated. In particular, for the duration of the first contest your score will be estimated on the current 30 test cases as announced above. This will allow for estimating your rank, as listed in the section standings. However, after the contest has finished your final score and rankings will be determined by running your final submission on 150 previously undisclosed input graphs. Out of these 150 test cases 90 will be random graphs (including 40 random graphs with maximum degree 8) and 60 will be complete graphs. Note that this implies that the final standings may change after the contest has finished. This change in evaluating the final score has been decided in agreement with AtCoder Inc. and became necessary to penalize excessive code tuning which is specific to the current 30 test graphs.

Input

Inputs are given in the following format through the standard input. All the inputs have integer values.

|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| and |E| denote the total number of vertices and edges of the graph G, respectively.
  • The line u_i, v_i, w_i means that the vertex u_i and the vertex v_i of the graph G are connected by an edge of weight w_i.
  • |V_{emb}| and |E_{emb}| denote the total number of vertices and edges of the graph G_{emb}, respectively.
  • The line a_i, b_i means that the vertex a_i and the vertex b_i of the graph G_{emb} is connected by an edge.

Constraints for the Graph 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.
  • The graph G is connected.

Constraints for the Graph G_{emb}

  • G_{emb} is a square King's graph.
  • 4 \leq |V_{emb}| \leq 3.6 \times 10^3 and |V_{emb}| is a square number.
  • |V| \leq |V_{emb}|
  • 1 \leq a_i \lt b_i \leq |V_{emb}|

Output

Output should be in the following format and should be processed through the standard output.

s_1 t_1
s_2 t_2
:
s_{|V|} t_{|V|}
  • The line s_i, t_i means that the vertex s_i of the graph G is assigned to the vertex t_i of the graph G_{emb}.
  • All the vertices in the graph G should be assigned to vertices in the graph G_{emb} and the relation should be one to one. For the detail, see Constraints for Output.

Constraints for Output

  • Output should consist of |V| lines.
  • 1 \leq s_i \leq |V|
  • 1 \leq t_i \leq |V_{emb}|
  • If i \neq j, s_i \neq s_j and t_i \neq t_j.

How are the Input Graphs G Generated?

For all the test cases, a given graph G is either a random graph or a complete graph. In what follows, we briefly explain how these graphs are generated. For details see the sample code.

Random Graph

  • First, a tree with |V| vertices is generated randomly. Subsequently, |E| - |V| + 1 edges are randomly added to the tree. Finally, a weight of a random value is assigned to each edge.
  • Furthermore, 8 random graphs will have an additional constraint. Their maximum degree is at most 8. These graphs are created by randomly adding vacant edges, only between vertices whose degree is smaller than 8.

Complete Graph

  • A weight of a random value is assigned to each edge 1 \leq u \lt v \leq |V|.

Input Example 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

Output Example 1

1 1
2 2
3 5

This input example corresponds to the schematic figure in the beginning of this problem page.

To demonstrate how this output is scored, let us consider the edge (1, 3) of the graph G that is in the fourth line in the input example. We now determine, whether its weight value 4 should be added to the score. To this end we consider the first and the third line of the output example. The first line specifies that the vertex 1 of the graph G is assigned to the vertex 1 of the graph G_{emb}. The third line specifies that the vertex 3 of the graph G is assigned to the vertex 5 in the graph G_{emb}. Finally, we check whether the corresponding vertex pair (1,5) of G_{emb} is connected by an edge. This is confirmed by the 8th line in the input file. Therefore, the corresponding weight value should be added to the total score.

In this output example, every connected vertex pair of graph G is assigned to a connected vertex pair of graph G_{emb}. Therefore, the total score is the sum of all weight values which add up to 7.

Input Example 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

Output Example 2

1 10
2 9
3 17
4 11
5 2
6 1
7 18

This input example corresponds to the following schematic figure.

Generator, Tester, and Reference

A generator and tester for this problem can be downloaded through the following link.

For a previous study of this problem, see:

　　

H. Neven, et al., "NIPS 2009 demonstration: Binary classification using hardware implementation of quantum annealing." Quantum (2009): 1-17.