题解 P5361 【[SDOI2019]热闹又尴尬的聚会】

· · 题解

题目大意：给定无向简单图，你需要构造如下两个点集：

1、使得其点导出子图中度数最小的点尽量大。设这个度数为p。

2、求一个尽可能大的的独立集。设独立集大小为q。

则需要满足：n/(p+1)<=q，n/(q+1)<=p。这里的除法是下取整。

哈？最大独立集？！神仙sdoi居然出npc问题。

看起来是一道二合一，而且一时半会想不出为什么要这么合对吧。

那我们开始冷静分析一波。

首先你会发现，第一问求出一个最大的p是很简单的：只需要从全集出发，每次删掉一个度数最小的点，更新答案，并更新其余点的度数即可。我们能很容易地用堆维护这个过程。

证明也很简单：你对当前点集求了个答案，但是你有梦想觉得说不定还能更大些，那怎么办？当然是先无脑把度数最小的点删掉了，因为如果能通过删点使得答案变大，这个点显然一定不会在点集中。

而第二问呢？求最大独立集是不可能求的，这辈子不可能求的。我们只能想办法去求一些近似解。

最大独立集其实有多种近似算法，比如：

1、随机一个排列，按照排列的顺序往集合里加点，能加就加。

2、对1算法进行爬山/退火。

3、每次选一个度数最小的点扔进独立集中，把它相连的点全删掉。

你随便写了一个近似算法，本不抱有希望能a甚至像我一样做好了a不掉就退役的打算，然后你惊奇地发现你a了。

这一是因为题目中给出的界其实很松，二是因为这些近似算法其实都能得出蛮不错的解，三是因为数据是随的。

算法1和2是随机算法这里就不多说了。

这里主要说明一下：算法3是100%保证正确性的！

原因如下：

你每次加入一个度数最小的点时，它的度数一定不超过p，否则当前剩余的点就是第1问的一个更优的解，说明你第一问求错了。

因此，每加入一个点，最多删掉p个点。

这样构造出来的q>=n/(p+1)，恰好是题目中给出的式子，而且注意这里是上取整因此不存在差1之类的细节问题。

这个过程也可以很容易地用堆维护。

（其实据说不需要堆，实现得好可以做到线性。）

哦对了，别忘了io优化。

#include<bits/stdc++.h>
using namespace std;
char buf[100000],*buff = buf + 100000;
#define gc (buff == buf + 100000 ? (fread(buf,1,100000,stdin),buff = buf) : 0,*buff++)
char bb[10000010],*bbb = bb;
#define pc(x) (*(bbb++) = (x))
inline int read(){
    int x = 0,c = gc;
    while(!isdigit(c)) c = gc;
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
    return x;
}
inline void print(int q){
    if(q >= 10) print(q / 10);
    pc(q % 10 + '0');
}
int t,n,m;
struct edge{
    int to,nxt;
}e[200010];
int cnt,fir[10010],ds[10010],nwd[10010];
inline void ins(int u,int v){
    e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
    e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;
    ++ds[u];++ds[v];
}
int p1,p2,dlj[10010],shan[10010],wz,ft;
bool d1[10010],d2[10010];
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
priority_queue<pii > q;
int main(){
    int i,j;
    t = read();
    while(t--){
        memset(fir,0,sizeof(fir));memset(dlj,0,sizeof(dlj));memset(d1,0,sizeof(d1));memset(d2,0,sizeof(d2));memset(ds,0,sizeof(ds));memset(nwd,0,sizeof(nwd));memset(shan,0,sizeof(shan));cnt = p1 = p2 = wz = ft = 0;
        n = read();m = read();
        for(i = 1;i <= m;++i) ins(read(),read());
        while(!q.empty()) q.pop();
        for(i = 1;i <= n;++i) nwd[i] = ds[i],q.push(mp(-nwd[i],i));
        while(!q.empty()){
            pii p = q.top();q.pop();
            if(-p.fi != nwd[p.se]) continue;
            if(-p.fi >= p1){
                p1 = -p.fi;
                wz = ft;
            }
            shan[++ft] = p.se;d1[p.se] = 1;
            for(i = fir[p.se];i;i = e[i].nxt) if(!d1[e[i].to]){
                --nwd[e[i].to];
                q.push(mp(-nwd[e[i].to],e[i].to));
            }
        }
        while(!q.empty()) q.pop();
        for(i = 1;i <= n;++i) nwd[i] = ds[i],q.push(mp(-nwd[i],i));
        while(!q.empty()){
            pii p = q.top();q.pop();
            if(-p.fi != nwd[p.se]) continue;
            if(d2[p.se]) continue;
            dlj[++p2] = p.se;d2[p.se] = 1;
            for(i = fir[p.se];i;i = e[i].nxt) if(!d2[e[i].to]){
                d2[e[i].to] = 1;
                for(j = fir[e[i].to];j;j = e[j].nxt) if(!d2[e[j].to]){
                    --nwd[e[j].to];
                    q.push(mp(-nwd[e[j].to],e[j].to));
                }
            }
        }
        memset(d1,0,sizeof(d1));
        for(i = 1;i <= wz;++i) d1[shan[i]] = 1;
        print(n - wz);pc(' ');for(i = 1;i <= n;++i) if(!d1[i]) print(i),pc(' ');pc('\n');
        print(p2);pc(' ');for(i = 1;i <= p2;++i) print(dlj[i]),pc(' ');pc('\n');
    }
    fwrite(bb,1,bbb - bb,stdout);
    return 0;
}