ARC161D

题意

定义一张简单无向图的 密度 为：\(\displaystyle M(G = \{V,E\}) = \frac{|E|}{|V|}\)。

给定 \(N,D\)，任务是构造一张点数为 \(N\)，边数为 \(ND\) 的简单无向图 \(G = (V, E)\)，满足以下条件：

• 对于 \(V\) 的每一个非空真子集 \(X\)，满足 \(G\) 的关于 \(X\) 的导出子图的密度 严格小于 \(D\)。

导出子图：保留每一条 \(E\) 中两个顶点都属于 \(X\) 的边所形成的图。

若有解，输出方案。否则输出 No。

题解

考虑尽可能的均匀度数，发现总度数为 \(2ND\)，平均下来就是 \(\dfrac{2ND}{N} = 2D\)。

那么现在的问题就转化为：构造 \(ND\) 个二元组 \((A_1,B_1), (A_2,B_2), \dots, (A_{ND}, B_{ND})\)，满足对于每一个 \(1 \leq i \leq ND\)，满足 \(A_i < B_i\)，并且对于每一对 \((i, j)(1 \leq i < j \leq ND)\) 满足 \((A_i,B_i) \neq (A_j,B_j)\)。并且对于每一个 \(k(1 \leq k \leq N)\)，满足 \(\displaystyle \sum_{i = 1}^{ND} [A_i = k] + [B_i = k] = 2D\)。

考虑对于每一个点 \(i\)，向前 \(D\) 个，后 \(D\) 个连边（如果中途没有再左的节点就是 \(N\)，右边同理），发现会有 \(2ND\) 条边，我们发现会有一半重复的，因为要求的图是简单的，所以 \((u, v)\) 和 \((v, u)\) 都会在这 \(2ND\) 条边中。

所以最后的边数为 \(\dfrac{2ND}{2} = ND\)，容易发现没有重边，且每一个点的度数为 \(2D\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define rep(i, l, r) for(int i = l;i <= r; ++ i)
#define per(i, r, l) for(int i = r;i >= l; -- i)
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
set < pair < int, int > > st;
inline void add_edge (int u, int v) {
	if (u > v) swap (u, v);
	st.insert (make_pair (u, v)); 
}
int n, d;
signed main () {
	n = read (), d = read ();
	if (2 * d + 1 > n) {
		printf ("No\n");
		return 0;
	}
	printf ("Yes\n");
	rep (i, 1, n) {
		int nw = i;
		rep (j, 1, d) {
			nw --;
			if (nw == 0) nw = n;
			add_edge (i, nw);
		}
		nw = i;
		rep (j, 1, d) {
			nw ++;
			if (nw == n + 1) nw = 1;
			add_edge (i, nw);
		}
	}
	for (pair < int, int > e : st) {
		printf ("%d %d\n", e.first, e.second);
	}
	return 0;
}