题解：P16941 「LAOI-18」Locus

Dr_KC_Haus · 2026-06-29 19:10:06 · 题解

其实这道题要求计算一个特定构造的无向图的‌全局最小割‌。答案是：

::::success[n - 2 - \lfloor \frac{n}{3} \rfloor]{open}

• 在该图中，全局最小割的大小等于顶点的最小度数。

:::info[为什么“全局最小割的大小等于顶点的最小度数”？]{open} 众所周知，在一个非常稠密的图中，就是说大多数点对之间都有边，全局最小割通常等于图中‌度数最小的顶点的度数‌。

如果我们把某个顶点 v 单独作为一个集合 S = \{ v \}，其余顶点作为 T，那么割的大小就是 v 的度数：deg(v)。

在这个问题中，“不整除”是常态，“整除”是少数情况，所以图很稠密。那么就可以证明，该图的全局最小割大小确实等于最小度数 \min_{v \in V} \deg(v)。 :::

• 顶点 3 是图中最小的数，拥有最多的倍数，就是说最多的“非边”连接，因此它的度数最小。

• 推导：

  • 从 3 到 n，总共 n - 2 个顶点。
  • 与 3 没有边‌的顶点数，就是 3 的倍数，不包含自身：\lfloor \frac{n}{3} \rfloor - 1。
  • ::::

:::success[AC Code]

#include<bits/stdc++.h>
int main(){
    long long n;
    std::cin>>n;
    std::cout<<n-2-n/3;
}

:::