算法
(图的构造) $O(N^2)$
先考虑 $K$ 的上下限
$K$ 的下限是 $0$,完全图
$K$ 的上限是 $\frac{(N - 1)(N - 2)}{2}$,菊花图
为啥 $\frac{(N - 1)(N - 2)}{2}$ 是上限?
很简单,因为 $N$ 个点有 $\frac{N(N - 1)}{2}$ 个点对,而距离为 $1$ 的点对最少为 $N - 1$ 个(图是连通的)
$$ \frac{N(N - 1)} {2} - \left( {N - 1} \right) = \frac{{{N^2} - 3N + 2}} {2} = \frac{{\left( {N - 1} \right)\left( {N - 2} \right)}} {2} $$
要构造上限 $-1$ 的图只需如下操作
要构造上限 $-2$ 的图只需如下操作
要构造上限 $-x$ 的图只需对这些发散出去的点连 $x$ 条边即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using P = std::pair<int, int>;
int main() {
int n, k;
cin >> n >> k;
int mx = (n - 1) * (n - 2) / 2;
if (mx < k) {
puts("-1");
return 0;
}
vector<P> ans;
rep(i, n - 1) {
ans.emplace_back(i + 1, n);
}
int add = mx - k;
vector<P> edge;
rep(i, n - 1)rep(j, i) edge.emplace_back(i + 1, j + 1);
rep(i, add) ans.push_back(edge[i]);
cout << ans.size() << '\n';
rep(i, ans.size()) {
cout << ans[i].first << " " << ans[i].second << '\n';
}
return 0;
}
^_^