题解 P6269 【[SHOI2002]空中都市】

图兰定理板子awa

珂能会有更好的阅读体验

图兰定理：若图 $G$ 中有 $n$ 个点，且完全图 $K_{r}$ 不是 $G$ 的子图，则 $G$ 中的边数最多为 $\left\lfloor\left(1-\dfrac{1}{r-1}\right)\cdot\dfrac{n^2}{2}\right\rfloor$。

本题就是 $r=3$ 的情况，也就是不存在三角形。此时最大边数为：$\left\lfloor\dfrac{n^2}{4}\right\rfloor$。

这里证明一下 $r=3$ 时的情况awa。

首先给出构造：我们把 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 个点放在「左边」，$\left\lceil\dfrac{n}{2}\right\rceil$个点放在「右边」，再将「左边」的每个点都与「右边」的每个点连上一条边。

此时，图 $G$ 中不存在两两相连的三个点，且总边数为 $\left\lfloor\dfrac{n}{2}\right\rfloor\cdot\left\lceil\dfrac{n}{2}\right\rceil=\left\lfloor\dfrac{n^2}{4}\right\rfloor$。

下面证明这种构造的确是最优的构造。

首先这 $n$ 个点中必有一个点的度数最大，记为 $A$。设 $\deg(A)=k$。

设与 $A$ 相连的这 $k$ 个点分别为 $B_1,B_2,\dots,B_k$，则 $\forall i,j\in[1,k],B_i$ 与 $B_j$ 不相连，否则 $A,B_i,B_j$ 构成了一个三角形，不符合条件。

于是 $\forall i\in[1,k]$，$B_i$ 至多与 $A$ 和剩下的 $n-k-1$ 个点相连，即 $\forall i\in[1,k],\deg(B_i)\le n-k$。

设剩下的 $n-k-1$ 个点分别为 $C_1,C_2,\dots,C_{n-k-1}$ ，由于 $A$ 是度数最大的，故 $\forall i\in[1,n-k-1]$，有 $\deg(C_i)\le \deg(A)=k$。

现在，我们来看一看整个图中有多少边。

此时图中边数为：

$\begin{aligned} |E|&=\dfrac{\sum\deg(X)}{2}\\ &=\dfrac{\deg(A)+\sum_{i=1}^{k}\deg(B_i)+\sum_{i=1}^{n-k-1}\deg(C_i)}{2}\\ &=\dfrac{k+k\cdot(n-k)+(n-k-1)\cdot k}{2}\\ &=k(n-k)\\ &\le\dfrac{n^2}{4} \end{aligned}$

最后一步是用了一下基本不等式放缩，取等条件为 $k=\left\lfloor\dfrac{n}{2}\right\rfloor$。

而已经给出了使总边数为 $\left\lfloor\dfrac{n^2}{4}\right\rfloor$ 的构造，又证明了边数不超过 $\left\lfloor\dfrac{n^2}{4}\right\rfloor$，所以本题答案就是 $\left\lfloor\dfrac{n^2}{4}\right\rfloor$。

极简代码：

#include<cstdio>
#include<cstdlib>

using namespace std;

int n;

int main(void){
    
    scanf("%d",&n);
    printf("%d\n",n*n/4);

    return 0;
}

$\text{PS}$：这里顺便提一下其他题解中打表发现的递推式awa。

@Warriors_Cat
&@idgg007&@yisu 巨佬的递推式：

设 $A_n$ 为点数为 $n$ 时的最大边数，则 $A_1=0,A_n=A_{n-1}+\left\lfloor\dfrac{n}{2}\right\rfloor$。

唔，其实我们是可以推出 $\{A_n\}$ 的通项就是 $A_n=\left\lfloor\dfrac{n^2}{4}\right\rfloor$ 的awa。

证明其实也很简单，用数学归纳法一步就完事啦qwq：

• $n=1$ 时，$A_1=0=\left\lfloor\dfrac{1^2}{4}\right\rfloor$，符合。
• 设 $n=k$ 时有 $A_k=\left\lfloor\dfrac{k^2}{4}\right\rfloor$，则当 $n=k+1$ 时：

$\begin{aligned} A_{k+1}&=A_k+\left\lfloor\dfrac{k+1} {2}\right\rfloor\\ &=\left\lfloor\dfrac{k^2}{4}\right\rfloor+\left\lfloor\dfrac{k+1} {2}\right\rfloor \end{aligned}$

分类讨论一下：当 $2|k$ 时，

$\begin{aligned} \left\lfloor\dfrac{k^2}{4}\right\rfloor+\left\lfloor\dfrac{k+1} {2}\right\rfloor&=\dfrac{k^2}{4}+\dfrac{k}{2}=\dfrac{k^2+2k}{4}\\ &=\dfrac{(k+1)^2-1}{4}=\left\lfloor\dfrac{(k+1)^2}{4}\right\rfloor \end{aligned}$

（用了一下熟知结论：奇数的平方模 $4$ 余 $1$）

当 $2\nmid k$ 时，

$\begin{aligned} \left\lfloor\dfrac{k^2}{4}\right\rfloor+\left\lfloor\dfrac{k+1} {2}\right\rfloor&=\dfrac{k^2-1}{4}+\dfrac{k+1}{2}\\ &=\dfrac{k^2+2k+1}{4}=\left\lfloor\dfrac{(k+1)^2}{4}\right\rfloor \end{aligned}$

于是 $A_{k+1}=\left\lfloor\dfrac{(k+1)^2}{4}\right\rfloor$。

由数学归纳法知 $\forall n\in \mathbb N^*,A_n=\left\lfloor\dfrac{n^2}{4}\right\rfloor$。

所以说这个递推式和图兰定理其实是一样的啦QwQ。