欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

vijos2054 SDOI2019 热闹的聚会与尴尬的聚会

程序员文章站 2022-06-21 22:44:45
题目链接 思路 首先观察题目最后的式子$\lfloor \frac{n}{p + 1} \rfloor \le q$ 并且$\lfloor \frac{n}{q+1} \rfloor \le p$。 这个式子其实就是告诉我们$p$和$q$都要尽量大。 然后这道题就可以分成两个小题: 1.求一个子图, ......

思路

首先观察题目最后的式子\(\lfloor \frac{n}{p + 1} \rfloor \le q\) 并且\(\lfloor \frac{n}{q+1} \rfloor \le p\)

这个式子其实就是告诉我们\(p\)\(q\)都要尽量大。

然后这道题就可以分成两个小题:

1.求一个子图,使得图中最小度数最大。

2.求最大独立集。

先看第一个问题:

可以贪心的每次将度数最小的点删去。剩下的点中度数最小的那个就是当前图的贡献。然后找一个最大的贡献就是答案。

第二个问题

求一般图的最大独立集。。。不太可能。

但是这个题目的限制并没有这么严格。只要满足\(\lfloor \frac{n}{p + 1} \rfloor \le q\)即可。

每次将度数最小的点加入独立集。然后将与该点所连的点全部删去。

可以发现,这样加到独立集中点的度数一定小于等于\(p\)(否则p就可以更大了)。所以每次最多删去\(p\)个点。最少可以删\(\lceil \frac{n}{p} \rceil\)次。也就是说最少可以加入这些点。所以这种做法肯定是满足\(\lfloor \frac{n}{p + 1} \rfloor \le q\)的。

代码

/*
* @author: wxyww
* @date:   2019-05-11 14:54:21
* @last modified time: 2019-05-11 15:27:46
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 100010;
#define pi pair<int,int>
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
priority_queue<pi,vector<pi>,greater<pi> >q;
struct node {
    int v,nxt;
}e[n << 1];
int head[n],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int vis[n],du[n],tsd[n],bz[n],ans[n],anss[n];
int main() {
    // freopen("day2t1.in","r",stdin);
    int t = read();
    while(t--) {

        memset(vis,0,sizeof(vis));
        memset(du,0,sizeof(du));
        memset(bz,0,sizeof(bz));
        ejs = 0;memset(head,0,sizeof(head));

        int n = read(),m = read();
        for(int i = 1;i <= m;++i) {
            int u = read(),v = read();
            add(u,v);add(v,u);
            du[u]++,du[v]++;
        }

        for(int i = 1;i <= n;++i) tsd[i] = du[i];


        for(int i = 1;i <= n;++i) q.push(make_pair(du[i],i));

        int ansjs = 0,js = 0,mx = 0;
        while(!q.empty()) {
            int d = q.top().first,u = q.top().second;
            q.pop();
            vis[u] = 1;
            if(du[u] != d) continue;
            if(d > mx) {
                // puts("!!!");
                // printf("%d\n",js);
                mx = d;
                ansjs = js;
            }
            ans[++js] = u;
            for(int i = head[u];i;i = e[i].nxt) {
                int v = e[i].v;
                if(vis[v]) continue;
                du[v]--;q.push(make_pair(du[v],v));
            }
        }
        memset(vis,0,sizeof(vis));
        for(int i = 1;i <= n;++i) q.push(make_pair(tsd[i],i));
        js = 0;
        while(!q.empty()) {
            int u = q.top().second,d = q.top().first;
            q.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            anss[++js] = u;
            if(d != tsd[u]) continue;
            // puts("!!!");
            for(int i = head[u];i;i = e[i].nxt) {
                int v = e[i].v;
                // puts("!!!");
                if(vis[v]) continue;
                vis[v] = 1;
                // printf("%d\n",v);
                for(int j = head[v];j;j = e[j].nxt) {
                    int vv = e[j].v;
                    if(vis[vv]) continue;
                    --tsd[vv];q.push(make_pair(tsd[vv],vv));
                }
            }
        }
        // puts("!!");
        for(int i = 1;i <= ansjs;++i) bz[ans[i]] = 1;
        printf("%d ",n - ansjs);
        for(int i = 1;i <= n;++i) if(!bz[i]) printf("%d ",i);
        puts("");
        printf("%d ",js);
        for(int i = 1;i <= js;++i) printf("%d ",anss[i]);
        puts("");

    }

    return 0;
}