目录
显示
题目链接
https://www.luogu.com.cn/problem/P3524
题解
早上杨主力讲课的时候讲到了这题,所以过来补题。
为了方便起见,我们令 \(n=3k\),即我们需要找到一个大小为 \(k\) 的团。
我们首先按题意将点分为两类,团内点和团外点。显然从 \(2k\) 个团内点中任意挑出 \(k\) 个点作为答案肯定是一种合法方案。问题变成了我们怎么找到团内点。
注意到团内点有个性质,任意两个团内点之间一定有边相连。考虑利用这个性质排除团外点。
我们枚举点对 \((i,j)\),若 \(i,j\) 间没有边,则表示这两个点之间至少有一个点不是团内点。我们将这两个点都从图上移除。
这样势必会导致一些团内点被错误的删除。不过因为一次删除至多删掉一个团内点,而团外点也至多只有 \(k\) 个,因此我们至多删除 \(k\) 个团内点,从而留下的团内点不少于 \(k\) 个,刚好符合要求。
// Problem: P3524 [POI2011]IMP-Party // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3524 // Memory Limit: 64 MB // Time Limit: 1000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #include <iostream> using namespace std; int f[3005][3005],vis[3005]; int main() { ios::sync_with_stdio(false); int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; f[u][v]=f[v][u]=1; } for(int i=1;i<=n;i++) { if(vis[i])continue; for(int j=1;j<=n;j++) { if(i==j||vis[j])continue; if(!f[i][j]) { vis[i]=vis[j]=1; break; } } } int cnt=0; for(int i=1;i<=n;i++) if(!vis[i]) { cout<<i<<' '; cnt++; if(cnt==n/3)break; } return 0; }