CF41E 3-cycles 题解

题目链接：CF41E 3-cycles

题意：

最近，Berland的科学家们在研究中发现古代Berland有 $n$ 个城市，它们通过双向路径相连。任意两个城市之间最多只有一条路径相连，且没有路径将城市与自身相连。根据众所周知的传统，道路网络的建设是为了确保不可能选择三个城市，其中每个城市都可以直接到达其他任何一个城市。也就是说，不存在长度为 $3$ 的环。不幸的是，道路地图并没有保存到现在。现在科学家们想知道古代Berland发展到了什么程度。帮助他们找出国家可能存在的最大道路数量，并恢复其中任意一种可能的道路地图。

输入格式：

第一行包含一个整数 $n$ $(1 \leq n \leq 100)$，表示Berland的城市数量。

输出格式：

第一行输出一个整数 $m$，表示Berland可能存在的最大道路数量。接下来的 $m$ 行每行包含两个整数，表示给定道路连接的城市编号。城市编号从 $1$ 到 $n$。如果有多种解决方案，请随意输出其中之一。

根据抽屉原理，每三个节点就有两个节点没有连边，我们可以认为这两个点在同一个抽屉里。

此时第三个小球一定在其他的抽屉里。如此可知，每个抽屉里的点都没有连边，而不同抽屉间存在连边。

可以发现，我们只需要两个抽屉就可以达到这个目的，而更多的抽屉反而会出现三元环，因此答案是二分图。

设二分图左部有 $x$ 个点，右侧有 $n - x$ 个点，考虑最大化他们的连边数量

$$\begin{aligned} x(n-x) = -x^2+nx && x_{\texttt{对称轴}} = \frac{n}{2} \end{aligned}$$

取 $x = \left\lfloor\dfrac{n}{2}\right\rfloor$ ，则答案为

$$\left\lfloor\dfrac{n}{2}\right\rfloor\times\left(n - \left\lfloor\dfrac{n}{2}\right\rfloor\right)$$

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; cout << ((n / 2) * (n - n / 2)) << '\n';
    for(int i = 1; i <= (n / 2); i++)
        for(int j = (n / 2 + 1); j <= n; j++) cout << i << ' ' << j << '\n';
    return 0;
}

可爱的小黑