题解 P6269 【[SHOI2002]空中都市】
WYXkk
·
·
题解
由 图兰定理（Turán's theorem） 可知，本题答案为 \left\lfloor\dfrac{n^2}4\right\rfloor。
\texttt{code(python):}
n=int(input())
print(n*n//4)
图兰定理：假如一个 n 个点的简单图中任意 3 个点都不互相连接，则其边数不超过 \left\lfloor\dfrac{n^2}4\right\rfloor。
图兰定理的证明：
取一个符合条件的图。记 d(X) 为与 X 相连的边的数量，称为 X 的度数。
假设所有 n 个点中，A 的度数最大，为 k，B_1,B_2,\cdots,B_k 与 A 相连，C_1,C_2,\cdots,C_{n-k-1} 与 A 不相连。
由于 A 与 B_1,B_2,\cdots,B_k 都有连边，假如存在 B_iB_j 这条边，那么 AB_iB_j 三个点互相连接，矛盾。因此 B_i 之间没有连边，故 d(B_i)\le n-k（至多与所有 C_j 和 A 连边）。
同时，由于 d(A) 最大，为 k，故 d(C_j)\le k。
因此，设边数为 e，则
\begin{aligned}e&=\dfrac{\sum d(X)}2\\&=\dfrac{d(A)+\sum\limits_{i=1}^kd(B_i)+\sum\limits_{j=1}^{n-k-1}d(C_j)}2\\&\le\dfrac{k+k\times(n-k)+(n-k-1)\times k}2\\&=k\times(n-k)\\&\le\left\lfloor\dfrac{n^2}4\right\rfloor\end{aligned}
记 k=\left\lfloor\dfrac n2\right\rfloor，则当且仅当图为 K_{k,n-k}，即两边点数分别为 k 和 n-k 的完全二分图时取到等号。