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;
}
可爱的小黑