其实这道题要求计算一个特定构造的无向图的全局最小割。答案是：
对于 的解释：
- 在该图中，全局最小割的大小等于顶点的最小度数。
为什么“全局最小割的大小等于顶点的最小度数”？
众所周知，在一个非常稠密的图中，就是说大多数点对之间都有边，全局最小割通常等于图中度数最小的顶点的度数。
如果我们把某个顶点 单独作为一个集合 ，其余顶点作为 ，那么割的大小就是 的度数：。
在这个问题中，“不整除”是常态，“整除”是少数情况，所以图很稠密。那么就可以证明，该图的全局最小割大小确实等于最小度数 。
-
顶点 是图中最小的数，拥有最多的倍数，就是说最多的“非边”连接，因此它的度数最小。
-
推导：
- 从 到 ，总共 个顶点。
- 与 没有边的顶点数，就是 的倍数，不包含自身：。
- 的度数，就是割的大小：。
AC Code
#include<bits/stdc++.h>
int main(){
long long n;
std::cin>>n;
std::cout<<n-2-n/3;
}
暂无评论