[SDOI2019] 热闹的聚会与尴尬的聚会

题意:

你有n个好友,他们之间有m对关系$(u,v)$表示u和v互相认识,认识没有传递性。

现在你想组织一场热闹的聚会和一场尴尬的聚会,定义如下:

  • 一场热闹度为p的聚会请来了任意多位好友,对于每一位到场的好友来说都有至少p位他认识的好友也参加了聚会,且至少对于一位到场的好友来说现场恰好有p位他认识的好友;
  • 一场尴尬度为q的聚会请来了恰好q位好友,且他们两两互不认识。

这两场聚会之间没有任何联系。

你希望p和q满足$\lfloor \frac{n}{p+1}\rfloor \leq q$且$\lfloor \frac{n}{q+1}\rfloor \leq p$,求一种合法方案。

$T\leq 32,n\leq 10000,m\leq 10^{5}$。

 

题解:

首先发现对于任意p/q,q/p越大越优,所以原问题可以拆成求最大的p和最大的q。

考虑求最大的p,显然可以依次尝试删除图中度数最小的点,尽管删除点数越多答案不一定越优,但记录最大答案及其删除个数即可。

考虑求最大的q,贪心的想法是依次取图中度数最小的点,并删除它和所有与它相邻的点。

但显然这样求出的并不是最大独立集。因为求一般图最大独立集是个NP问题。

不过,我们本身要求的并不是最大的q,而是任意一个满足$\lfloor \frac{n}{p+1}\rfloor \leq q$且$\lfloor \frac{n}{q+1}\rfloor \leq p$的q,所以有一个奇妙的结论:这样贪心是100%正确的。

证明:考虑p算法的过程,我们每次删除的点的度数一定$\leq p$。

而q算法删的点的度数比p只少不多,也就是说对于q中每次操作至多会删掉p+1个点。

那么显然q算法至少会运行$\lceil \frac{n}{p+1}\rceil$次,这也对应着该算法求出的q的下界。

于是求出的p和q一定满足题目中的限制条件($(p+1)(q+1)>n$时两个条件均满足),证毕。

复杂度$O(T(n+m)logn)$(大概吧),需要稍加优化。

(也许运行q算法时直接删点不更新边权也是对的,但我并不想证明)

 

套路:

  • 在有某些限制条件时瞎蒙一个贪心很可能是对的;
  • 构造题可以考虑将若干个限制条件合并成一个较宽松的限制条件,一般很少有人喜欢把下界卡死(大概吧)。

 

代码:

[SDOI2019] 热闹的聚会与尴尬的聚会
#include<bits/stdc++.h>
#define maxn 10005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl

using namespace std;
int to[maxm],nxt[maxm],hd[maxn],vis[maxn],cnt;
int A[maxn],B[maxn],deg[maxn],D[maxn];
priority_queue<pair<int,int> > Q;
map<pair<int,int>,int> M;

inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline void addedge(int u,int v){
    to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt;
    to[++cnt]=u,nxt[cnt]=hd[v],hd[v]=cnt;
}

int main(){
    int T=read();
    while(T--){
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        memset(hd,0,sizeof(hd));
        memset(deg,0,sizeof(deg));
        memset(vis,0,sizeof(vis));
        M.clear(),cnt=0;
        while(!Q.empty()) Q.pop();
        int n=read(),m=read();
        for(int i=1;i<=m;i++){
            int u=read(),v=read(); if(u>v) swap(u,v);
            if(M[mp(u,v)]) continue;
            else addedge(u,v),M[mp(u,v)]=1,deg[u]++,deg[v]++;
        }
        memcpy(D,deg,sizeof(deg));
        for(int i=1;i<=n;i++) Q.push(mp(-deg[i],i));
        int ans=0,endpos=0;
        while(!Q.empty()){
            int u=Q.top().second,d=-Q.top().first; 
            Q.pop(); if(vis[u]) continue;
            vis[u]=1,A[++A[0]]=u;
            if(ans<-Q.top().first)
                ans=-Q.top().first,endpos=A[0];
            for(int i=hd[u];i;i=nxt[i])
                if(!vis[to[i]]) 
                    Q.push(mp(-(--deg[to[i]]),to[i]));
            
        }
        memcpy(deg,D,sizeof(D));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) Q.push(mp(-deg[i],i));
        while(!Q.empty()){
            int u=Q.top().second,d=-Q.top().first; 
            Q.pop(); if(vis[u]) continue;
            vis[u]=1,B[++B[0]]=u;
            for(int i=hd[u];i;i=nxt[i]){
                int v=to[i];
                if(vis[v]) continue;
                vis[v]=1;
                for(int j=hd[v];j;j=nxt[j]){
                    int w=to[j];
                    if(vis[w]) continue;
                    Q.push(mp(-(--deg[w]),w));
                }
            }
        }
        printf("%d",n-endpos);
        for(int i=endpos+1;i<=n;i++) printf(" %d",A[i]);
        printf("\n");
        printf("%d",B[0]);
        for(int i=1;i<=B[0];i++) printf(" %d",B[i]);
        printf("\n");
    }
    return 0;
}
热闹的聚会与尴尬的聚会

 

上一篇:Luogu5358 [SDOI2019]快速查询


下一篇:[SDOI2019] 快速查询