问题
下面假设我们有两张图。第一张图 G=(V, E) 由一组顶点组成 V 和边缘 E。第二张图 G_{emb} = (V_{emb}, E_{emb}) 也由一组顶点组成 V_{emb} 和边缘 E_{emb} 且应为正方形 国王图,顶点从左到右、从上到下标记,如下图所示。任务是找到地图 s 分配每个顶点 i\in V 到顶点的子集 s(i) ⊂ V_{emb} 这样:
- 对于任何顶点 i \in V 导出的子图 s(i) in G_{emb} 已连接;
- 子集 s(i), s(j) ⊂ V_{emb} 是互斥的,即对于任何 i,j \in V 与 i\neq j 我们有 s(i)∩ s(j)=Ø;
- 对于任何顶点 i \in V 子集 s(i) 不能为空。

分数
对于单个输入图上的算法的每次运行,结果图获得的分数 s 评估如下:
- 初始分数为 已分配 5000 点。
- We add 100 指向每条边的初始分数 (i,j) \in E,如果对应的顶点集 s(i), s(j) ⊂ V_{emb} 由国王图的至少一条边连接 G_{emb}.
- 我们添加奖金 100000 点,如果算法找到地图 s 这样对于每条边 (i,j)\in E, the corresponding vertex sets s(i), s(j) ⊂ V_{emb} 由国王图的至少一条边连接 G_{emb}。 Note that finding a map s 可能无法在每个输入图上获得奖励分数。
- 大簇会受到减去的惩罚 ∑ _{u \in V} (|s(u)|-1) 得分。
- 分数变为 0 有下列情形之一的:
- 如果由任何顶点集导出的子图 s(i) in G_{emb} 已断开连接。参见下图中的示例1。
- 如果顶点集 s(i), s(j) 不是互斥的,即,如果任何顶点集 (i \neq j) overlap on some element. See Example 2 in the figure below.
- If the subset s(i) 为空,即 |s(i)| = 0.
- 此外,任何超出时间或内存限制的算法运行都不会影响您的最终得分。对于任何违反下面指定的输出格式的输出也是如此。

- 在比赛期间,我们将通过在 30 个输入图上运行您的算法来评估您的分数 G and adding up the corresponding score. This will allow for a preliminary estimate of your rank.
- 比赛结束后,您的最终得分和排名将通过运行您的最终提交来确定 150 previously undisclosed input graphs.
输入
Inputs are given in the following format through the standard input. All the inputs have integer values.
|V| |E|
u_1 v_1
u_2 v_2
:
u_{|E|} v_{|E|}
|V_{emb}| |E_{emb}|
a_1 b_1
a_2 b_2
:
a_{|E_{emb}|} b_{|E_{emb}|}
- |V| 和 |E| denote the total number of vertices and edges of the graph G。
- The line u_i, v_i means that the vertex u_i and the vertex v_i of the graph G 已连接。
- |V_{emb}| 和 |E_{emb}| denote the total number of vertices and edges of the graph G_{emb}。
- The line a_i, b_i means that the vertex a_i and the vertex b_i of the graph G_{emb} 通过边连接。
图上的约束 G
- 2 \leq |V| \leq 5 \times 10^2
- 1 \leq |E| \leq min ( \frac{|V| \times (|V|-1)}{2}, 2 \times 10^4 )
- 1 \leq u_i \lt v_i \leq |V|
- For any pair i \neq j, we have that either u_i \neq u_j or v_i \neq v_j.
- The graph G 已连接。
图上的约束 G_{emb}
- G_{emb} 是方形国王图。
- 4 \leq |V_{emb}| \leq 3.6 \times 10^3 和 |V_{emb}| is a square number.
- |V| \leq |V_{emb}|
- 1 \leq a_i \lt b_i \leq |V_{emb}|
输出
Output should be in the following format consisting of |V| lines and should be processed through the standard output.
n_1 x_{1,1} x_{1,2} ... x_{1,n_1}
n_2 x_{2,1} x_{2,2} ... x_{2,n_2}
:
n_{|V|} x_{|V|,1} x_{|V|,2} ... x_{|V|,n_{|V|}}
- The index i in n_{i} 表示 i-th vertex of graph G.
- n_{i} denotes the total number of vertices in s(i)⊂ V_{emb},分配给 i-th vertex of graph G.
- x_{i,j} 表示 j-th element of subset s(i),分配给 i-th vertex of graph G.
输出的约束
- Output should consist of |V| 行。
- 1 \leq n_i
- 1 \leq x_{i,j} \leq |V_{emb}|
- i \neq j or k \neq l implies that x_{i,k} \neq x_{j,l}
How are the Input Graphs G Generated
For evaluating your final score, we will run your algorithm on random input graphs G。 These graphs are generated as follows: First, a tree with |V| vertices is generated randomly.随后, |E| − |V| + 1 edges are randomly added to the tree. For details see the sample code.
输入示例 1
7 14 1 2 1 3 1 6 1 7 2 4 2 5 2 6 2 7 3 5 3 7 4 5 4 6 4 7 5 7 25 72 1 2 1 6 1 7 2 6 2 3 2 7 2 8 3 7 3 4 3 8 3 9 4 8 4 5 4 9 4 10 5 9 6 7 6 11 6 12 7 11 7 8 7 12 7 13 8 12 8 9 8 13 8 14 9 13 9 10 9 14 9 15 10 14 11 12 11 16 11 17 12 16 12 13 12 17 12 18 13 17 13 14 13 18 13 19 14 18 14 15 14 19 14 20 15 19 16 17 16 21 16 22 17 21 17 18 17 22 17 23 18 22 18 19 18 23 18 24 19 23 19 20 19 24 19 25 20 24 5 10 10 15 15 20 20 25 21 22 22 23 23 24 24 25
输出示例 1
3 14 15 20 1 19 1 9 1 23 1 18 1 25 1 13
The input example 1 from above is visualized in the figure below. The left side shows the input graph with 7 vertices, labeled by indices V1 to V7。右侧为King尺寸图 5\times5。地图 示例 1 的输出指定的 s 通过彩色框可视化。 For example, the vertex V1 of the input graph is mapped to a set of three vertices on the kings graph.

我们现在讨论分配给地图的分数 s 如输出示例 1 所示:
- 初始分数为 5000 点。
- We add 11 \times 100 = 1100 指向初始分数,即,如果对应的顶点集由 King 图的至少一条边连接,则输入图的每条边为 100 分。 To this end consider for example the edge between the vertex pair (V1, V2)。 Clearly, the corresponding vertex sets on the King's graph are connected.因此,我们为这条边加 100 分。另一方面,考虑顶点对 (V3, V5)。 King图上对应的顶点集不相连。因此,这条边对得分没有贡献,我们用红叉标记它。对输入图的每条边重复此过程,我们发现 11 此示例得分的边缘,而 3 边缘(用红叉标记)不得分。
- 输出示例1的奖励积分为 0 因为对应于输入图的某些边(如红十字标记)的顶点集不通过 King 的图的直接边连接。
- 我们减去 (3-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1)= 2 点,其中每个括号中的第一个数字对应于右侧每个顶点集中的元素数量。由于顶点设置,我们总共损失了 2 分 s(V1) 包含三个元素。
- 总共输出示例 1 分数,因为顶点集 s(i) 是互斥的并且每个顶点集 s(i) 导出国王图的连通子图。
输入示例 2
10 30 3 10 3 6 5 10 5 8 2 6 2 7 1 5 1 9 4 10 5 7 4 6 2 8 1 2 7 10 2 4 1 3 7 8 1 8 6 9 2 9 1 4 2 10 2 3 6 10 8 10 6 8 5 6 3 8 7 9 4 9 16 42 1 2 1 5 1 6 2 5 2 3 2 6 2 7 3 6 3 4 3 7 3 8 4 7 5 6 5 9 5 10 6 9 6 7 6 10 6 11 7 10 7 8 7 11 7 12 8 11 9 10 9 13 9 14 10 13 10 11 10 14 10 15 11 14 11 12 11 15 11 16 12 15 4 8 8 12 12 16 13 14 14 15 15 16
输出示例 2
1 5 2 7 10 1 1 1 2 1 12 1 6 1 15 1 9 1 4 4 3 8 11 14
输入示例2对应如下示意图。

示例代码和参考
- 示例代码,包括用于生成随机输入图和评估算法相应分数的源代码,可以通过以下方式下载 链接.
- 之前对图嵌入问题的研究,请参阅: