← 返回题目列表

AtCoder · kupc2013_g

G. 免费研究

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

狐狸二郎暑假在做免费研究。 我正在考虑最大独立集合問題的算法。 在最大独立集问题中,使用无向图作为输入。 当 G=(V,E) 。 G 的每个顶点被涂成白色或黑色,并且每条边的至少一个端点被涂成白色时,我们指的是一组黑色顶点。 它被称为独立集合。 例如,在下图中,给定一个像左图这样的图,如果对图的中间部分进行着色,则黑色顶点集将成为一个独立集,但另一方面,如果将其像图的右侧部分那样进行着色,则黑色顶点集不会成为独立集。 该问题的目的是找到一个元素数量最多的独立集合。 为了方便起见,用图 G 的最大独立集合的大小是 写为 A(G) 。

[原图]

不幸的是这个问题NP难 已知,在多项式时间内不太可能找到最优值。 因此,狐狸二郎设计了一种随机选择算法,虽然没有理论上的保证,但似乎确实有效。算法如下。

[二郎的算法] 令N=|V| 为图的顶点数。 最初,所有顶点都被漆成白色。 现在,在每个顶点 分配 1,2,…,N 编号,以便任意两个顶点具有不同的编号。 这时,N! = N \times (N-1) \times (N-2) \times … \times 1 有不同的分配方法, 我们将以统一的概率随机分配其中之一。 每个顶点 对于 v ,如果 与 v 相邻的所有顶点 分配给 w 如果你写 v 的编号是 w 当小于 将 v 漆成黑色。 (如果 如果没有与 v 相邻的顶点,则算法 假设 v 被漆成黑色。 )然后输出涂黑的顶点作为问题的解。

Jiro 算法的工作原理示例如下图所示。 当给出如图左侧的图时,我们为每个顶点分配一个数字(随机),然后将满足条件的顶点涂为黑色。

[原图]

从定义中我们可以看出,该算法涂黑的顶点集合是一个独立的集合。 创建完算法后,二郎显得信心十足,但在一旁观看的狐狸谢尔却突然与他对峙。 这样的算法永远不会产生好的解决方案。 Shieru 决定向狐狸二郎展示一个致命案件,但狐狸二郎并不相信。 令

E(G) 为 Jiro 算法输出的黑色顶点集的预期大小。 顶点数为 40 或更少 在的无向图中, 创建一个最大化A(G)-E(G) 并输出它。

入力形式

无输入。

出力形式

输出满足目的的图表。 图表的输出格式如下。

N
s_{11}s_{12}s_{13}…s_{1n}
s_{21}s_{22}s_{23}…s_{2n}
s_{31}s_{32}s_{33}…s_{3n}
…
s_{n1}s_{n2}s_{n3}…s_{nn}
n 是图中的顶点数。 s_{ij} 是表示图表中的连接关系的字符。 顶点 当 i 和 j 之间没有边缘时 s_{ij}=N 和 顶点 当 i 和 j 之间存在边缘时 s_{ij}=Y 。 由于限制和图的性质,必须满足以下条件。
  • 1 ≤ N ≤ 40
  • s_{ii} = N
  • s_{ij} = s_{ji}

採点方式

如果输出解是最优解,您将获得 500 分。 如果解不是最优解,则该问题的最优解为 作为 OPT ,score = X \times (A(G) - E(G)) / OPT 。这里 X 是 40 到 50 之间的固定值。 如果 score ≥ 20 然后,score 获取积分。 如果 score < 20 ,您将获得 0 分。

入出力例

下面显示了输入和输出的示例,但由于问题的性质,无法记录最优解的输出,因此这里我们将展示一个满足输出格式的非最优解的示例。

入力例 1


出力例 1

3
NYY
YNY
YYN

此输出表示 3 个顶点的完整图。在此图中 A(G) = E(G) = 1 并且远非致命病例。

入力例 2


出力例 2

3
NYN
YNY
NYN

此输出表示 3 顶点路径图。在此图中 A(G) = 2,E(G) = (1+1+1+1+2+2)/6 = 4/3 因此, A(G) - E(G) = 2/3 变为。