[洛谷 5361,loj 3113][SDOI2019]热闹的聚会与尴尬的聚会

题目链接

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

https://loj.ac/problem/3113

题解

两个问题能放在一道题里，说明这两个问题间应该存在点内在联系。

我们先看第一问。

第一问比较简单，我们每次从图上删除度数最小的点，并更新答案，即可确保 \(p\) 尽可能大。

而对于求最大独立集，NPC 是不可能做的，这辈子都不可能做的，有诸如模拟退火等近似算法（然而是否完全准确就不知道了）。

针对本题，我们有一种和解第一问差不多的方法：我们仍然每次挑出度数最小的点，把这个点加入独立集，并将与这个点直接相连的点从图中删掉。

可以证明，按照这个方法构造，一定可以满足题目所述限制。

证明如下：

我们每将一个点加入独立集，除去这个点本身外，最多会从图中删掉 \(p\) 个点（第一问的结论）。

于是有 \(q \geq \left \lceil \frac{n}{p+1} \right \rceil\)。

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
struct node
{
 int x,y;
 bool operator<(const node&a)const
 {
  return y>a.y;
 }
};
vector<int> e[10005];
int t[10005],t1[10005],t2[10005],vis[10005];
int ord[10005],res[10005],cnt;
priority_queue<node> q;
int main()
{
 ios::sync_with_stdio(false);
 int T;
 cin>>T;
 while(T--)
 {
  int n,m;
  int ansp=0,ansq=0,pos=0;
  cnt=0;
  cin>>n>>m;
  memset(t,0,sizeof(t));
  for(int i=1;i<=n;i++)
   vector<int>().swap(e[i]);
  for(int i=1;i<=m;i++)
  {
   int u,v;
   cin>>u>>v;
   e[u].push_back(v);
   e[v].push_back(u);
   t[u]++,t[v]++;
  }
  memcpy(t1,t,sizeof(t));
  memcpy(t2,t,sizeof(t));
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++)
   q.push({i,t[i]});
  ansp=q.top().y;
  while(!q.empty())
  {
   int u=q.top().x;
   q.pop();
   if(vis[u])continue;
   ord[++cnt]=u,vis[u]=1;
   int rp=q.top().y;
   if(rp>ansp)
    ansp=rp,pos=cnt;
   for(auto v:e[u])
   {
    t1[v]--;
    q.push({v,t1[v]});
   }
  }
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++)
   q.push({i,t[i]});
  while(!q.empty())
  {
   int u=q.top().x;
   q.pop();
   if(vis[u])continue;
   res[++ansq]=u,vis[u]=1;
   for(auto v:e[u])
    vis[v]=1;
  }
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=pos;i++)
   vis[ord[i]]=1;
  cout<<n-pos<<' ';
  for(int i=1;i<=n;i++)
   if(!vis[i])cout<<i<<' ';
  cout<<endl;
  cout<<ansq<<' ';
  for(int i=1;i<=ansq;i++)
   cout<<res[i]<<' ';
  cout<<endl;
 }
 return 0;
}