题解 CF232A 【Cycles】
Heartlessly
2019-06-18 16:24:15
## Description
构造一个无向图（没有自环），使这个无向图恰好有 $m$ 个三元环，输出这个无向图的 $01$ 矩阵。
$($无向图的顶点数不超过 $100,1 \leq m \leq 10^5)$
## Solution
从 $n$ 个点的完全图中任意选出 $3$ 个点都能组成三元环，所以一共有 $C_n^3$ 个三元环。
我们可以先构造出一个尽可能大的完全图，满足 $C_n^3 \leq m$ 。
我们只需要再使这个无向图增加 $m - C_n^3$ 个三元环即可。
考虑新加一个点，这个点与完全图中 $x$ 个点连边。从这 $x$ 个点中任意选出 $2$ 个点都能与这个新加的点构成三元环，所以就会增加 $C_x^2$ 个三元环。
我们可以把 $m - C_n^3$ 拆分成多个 $C_x^2$ 的和。
举个例子，当 $m = 15$ 时，我们可以先构造一个 $5$ 个点的完全图，共有 $C_5^3 = 10$ 个三元环（如图）。
这时我们还需要增加 $15 - 10 = 5$ 个三元环。
而 $4 = 3 + 1 + 1 = C_3^2 + 2C_2^2$，我们可以新加一个点 $6$，与 $1,2,3$ 连边，增加了 $3$ 个三元环。
再加一个点 $7$，与 $1,2$ 连边，增加了 $1$ 个三元环。
最后加一个点 $8$，与 $1,2$ 连边，增加了 $1$ 个三元环。
这样一共就有 $15$ 个三元环了。
注意拆分时要从大到小枚举 $x$，且 $x$ 的最大值为 $n - 1$，最小值为 $2$ 。用这种构造方法，最后的点数不会超过 $100$ 。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 100;
int n = 1, m, e[MAXN + 5][MAXN + 5];
inline int C(int n, int m) {//组合数，这道题只用到 m = 2 和 m = 3
if (m == 2) return n * (n - 1) / 2;
if (m == 3) return n * (n - 1) * (n - 2) / 6;
return -1;
}
int main() {
read(m);
for (; C(n, 3) <= m; ++n);//构造一个尽可能大的完全图
--n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
e[i][j] = e[j][i] = 1;//完全图中点与点之间连无向边
m -= C(n, 3);//需要增加的三元环个数
for (int i = n - 1; i > 1; --i)//从大到小枚举 x
for (; m >= C(i, 2); m -= C(i, 2)) {//如果足够分解
++n;//新建一个节点
for (int j = 1; j <= i; ++j) e[j][n] = e[n][j] = 1;
//新节点连向 1 ~ i，共 i 个点，增加了 C(i,2) 个三元环
}
write(n);
putchar('\n');
for (int i = 1; i <= n; ++i, putchar('\n'))
for (int j = 1; j <= n; ++j)
write(e[i][j]);
return 0;
}
```