摘要
题意: 一个 n 个点 m 条边的无向图 \(n\equiv 0(\bmod 3)\), 保证存在一个大小为 \(\frac{2}{3}n\) 的团, 要求输出一个大小为 \(\frac{1}{3}n\) 的团.\(n\leq 3000\).
这道题的特殊之处在于找团, 而它保证有一个 \(\frac{2}{3}n\) 大小的团, 却只让我们找一个 \(\frac{1}{3}n\) 的团. 这意味着我们在寻找的过程中可以舍弃一些点.
团中的点是两两相邻的, 因此我们直接枚举判断不相邻的两个点并直接舍掉. 每个点最多被舍掉一次. 考虑这样做的正确性. 你找到的两个点一定不可能同时是 \(\frac{2}{3}n\) 团中的点, 要么一个是团中的点一个不是, 要么两个都不是其中的点. 因此这个操作最多进行 \(\frac{1}{3}n\) 次, 每次取 2 个点, 最后剩下的 \(\frac{1}{3}\) 个点一定是一个团.
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e3+5;
- int n,m,e[N][N];
- bool v[N];
- int main(){
- iOS::sync_with_stdio(false);
- cin>>n>>m;
- for(int i=1;i<=m;i++){
- int u,v;
- cin>>u>>v;
- e[u][v]=e[v][u]=1;
- }
- for(int i=1;i<=n;i++){
- if(v[i])continue;
- for(int j=i+1;j<=n;j++)if(!v[j]&&!e[i][j]){
- v[j]=v[i]=1;break;
- }
- }
- int tot=0;
- for(int i=1;i<=n;i++){
- if(!v[i])cout<<i<<' ',++tot;
- if(tot*3==n)break;
- }
- return 0;
- }
- [POI2011]IMP-Party
来源: http://www.bubuko.com/infodetail-3092598.html