「Codeforces 232A」Cycles

Description

构造一个无向图（没有自环），使这个无向图恰好有 $m$ 个三元环，输出这个无向图的 $01$ 矩阵。

$($无向图的顶点数不超过 $100,1 \leq m \leq 10^5)$

Source

[Luogu]CF232A

[Codeforces]232A

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

#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;
}