[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据