AT_arc161_d [ARC161D] Everywhere is Sparser than Whole (Construction)

题目描述

我们将非空简单无向图的密度定义为 $\displaystyle\frac{(边数)}{(顶点数)}$。

给定正整数 $N,\ D$，请判断是否存在一个具有 $N$ 个顶点、$DN$ 条边的简单无向图 $G$，满足以下条件。若存在，请构造出任意一个满足条件的图。

条件： 记 $G$ 的顶点集合为 $V$。对于 $V$ 的任意非空真子集 $X$，由 $X$ 构成的 $G$ 的诱导子图的密度严格小于 $D$。

关于诱导子图的定义如下：

对图 $G$ 的顶点子集 $X$，由 $X$ 构成的诱导子图是指“顶点集合为 $X$，边集合为『属于 $G$ 且连接 $X$ 中两个顶点的所有边』的图”。注意，此条件中只考虑非空且不等于全集的顶点子集。

输入格式

输入从标准输入中给出，格式如下：

$N$ $D$

输出格式

若存在满足条件的简单无向图，则输出 Yes，否则输出 No。若输出 Yes，接下来输出 $DN$ 行，描述所构造的图，格式如下：

$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{DN}$ $B_{DN}$

• $1\ \leq\ A_i,\ B_i\ \leq\ N\ (1\ \leq\ i\ \leq\ DN)$
• $A_i\ \neq\ B_i\ (1\ \leq\ i\ \leq\ DN)$
• $\{A_i,\ B_i\}\ \neq\ \{A_j,\ B_j\}\ (1\ \leq\ i\ <\ j\ \leq\ DN)$
• 图的顶点编号为 $1$ 到 $N$。
• 第 $i$ 行输出表示第 $i$ 条边连接顶点 $A_i$ 与 $B_i$。
• 边的顺序（哪条边先输出）和每条边端点的顺序（先输出哪个顶点）没有限制。

样例 1

输入

3 1

输出

Yes
1 2
1 3
2 3

样例 2

输入

4 2

输出

No

说明/提示

限制条件

• $N\ \geq\ 1$；
• $D\ \geq\ 1$；
• $DN\ \leq\ 5\ \times\ 10^4$。

样例解释 1

输出的图的顶点集合为 $\{1,\ 2,\ 3\}$，边集合为 $\{(1,\ 2),\ (1,\ 3),\ (2,\ 3)\}$，满足简单图的定义。对非空真子集 $X$ 有 $6$ 种情况：

• 当 $X = \{1\},\ \{2\},\ \{3\}$ 时，诱导子图的边集合为空，密度为 $\displaystyle\frac{0}{1} = 0$；
• 当 $X = \{1,\ 2\},\ \{1,\ 3\},\ \{2,\ 3\}$ 时，诱导子图的边集合分别为 $\{(1,\ 2)\},\ \{(1,\ 3)\},\ \{(2,\ 3)\}$，密度均为 $\displaystyle\frac{1}{2}$。

所以所有诱导子图的密度都严格小于 $D = 1$，该图满足条件。

样例解释 2

不存在一个简单无向图同时满足 $4$ 个顶点和 $8$ 条边的要求。

翻译由 GPT-4o 提供。