CSP-S 提高级 · CSP 2020 提高级第一轮 第 8 题

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，$24$ 个顶点的二分图至多有（ ）条边。

这题本质是求固定和的两个数乘积最大，直接想到均值不等式：和定积最大当两数相等，所以把24平分，算出12×12即可。

很多同学会纠结是不是要枚举所有划分，或者误以为边可以在同一部分内部连。其实二分图定义已经锁死了边只能跨部分，不需要枚举；只要抓住"和固定乘积最大"这个核心，就能秒杀。

考点与概念

二分图是把顶点分成两个集合X和Y，且所有边都连接X和Y中的点，同一集合内不能有边。因此，n个顶点的二分图最多能连的边数，就是把这n个点切成两块，让两块之间的连线尽可能多——也就是两块大小越接近越好。

命题视角

命题人喜欢把图论概念和代数最值揉在一起考：先让你理解二分图只能"跨块连边"，再让你用"和定积最大"这个经典结论去算。坑点往往在选项里塞几个接近144但不是两个整数乘积的数（比如122），或者把块的大小拉得很开（比如20×4=80）来迷惑你。