[洛谷 3524,loj 2166][POI2011]Party

题目链接

https://www.luogu.com.cn/problem/P3524

https://loj.ac/problem/2166

题解

早上杨主力讲课的时候讲到了这题，所以过来补题。

为了方便起见，我们令 \(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;
}