P5361 题解

· · 题解

Solution

首先分析一下这个诡异的限制：\lfloor \frac{n}{p+1} \rfloor \le q 且 \lfloor \frac{n}{q+1} \rfloor \le p。

首先，如果 p+1 \nmid n，那么 \frac{n}{p+1} 就不是整数，因此 \frac{n}{p+1} < q+1。因此 \frac{n}{q+1} < p+1。必定有 \lfloor \frac{n}{q+1} \rfloor \le p。如果 p+1 \mid n，也就是 \frac{n}{p+1} \le q。于是 \frac{n}{p+1} < q+1 得到 \frac{n}{q+1} < p+1，也就是 \lfloor \frac{n}{q+1} \rfloor \le p。于是我们只需要满足第一个条件。

然后你发现，你让 p 和 q 分别取到最大值，那么肯定满足！

首先考虑怎么求 p 的最大值。考虑我们从 G 出发逐步调整。注意，为了让答案更大，当前度数最小节点必须删去，而删去其他节点是没有意义的。然后在这个过程中枚举最小度数的最大值即可。

第二问是一般图的最大独立集问题。据说它是 NPC 问题。

但是考虑到你并不一定要把最大独立集求出来。下面再给出一个算法：每次把度数最小的节点和它所有相邻节点取出来，并且把这个度数最小的节点放进独立集里面去。由于每个时刻度数最小点的度数必然小于等于 p，因此这一步最多删掉 p+1 个点。所以你一共最少可以进行 \lceil \frac{n}{p+1} \rceil \ge \lfloor \frac{n}{p+1} \rfloor 步。

这个过程有点像 Dijkstra。于是你可以借鉴一下。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e4+10,MAXM=1e5+10;
int T,n,m,Deg[MAXN],deg[MAXN],in[MAXN];
pair<int,int> E[MAXM]; 
vector<int> G[MAXN];
int read(void) {
    int s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s;   
}
struct Node {int u,dis;};
bool operator <(Node A,Node B) {return A.dis>B.dis;}
int vis[MAXN],res;
vector<int> ot,ans;
void solve(int mn=-1) {
    priority_queue<Node> q;
    ffor(i,1,n) vis[i]=0,deg[i]=Deg[i];
    ffor(i,1,n) q.push({i,deg[i]});
    int flg=0;
    while(!q.empty()) {
        int u=q.top().u;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        if(mn==-1) res=max(res,deg[u]);
        else {
            if(deg[u]>=mn) flg=1;
            if(flg) ot.push_back(u);    
        }
        for(auto v:G[u]) if(vis[v]==0) deg[v]--,q.push({v,deg[v]});
    }
    return ;
}
void Solve(void) {
    ffor(i,1,n) vis[i]=0,deg[i]=Deg[i];
    priority_queue<Node> q;
    ffor(i,1,n) q.push({i,deg[i]});
    while(!q.empty()) {
        int u=q.top().u; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        ans.push_back(u);
        for(auto v:G[u]) {
            if(vis[v]==0) {
                vis[v]=1;
                for(auto t:G[v]) if(vis[t]==0) deg[t]--,q.push({t,deg[t]});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    T=read();
    while(T--) {
        n=read(),m=read(),ot.clear();
        ffor(i,1,n) deg[i]=0,G[i].clear();
        ffor(i,1,m) {int u=read(),v=read();E[i]={min(u,v),max(u,v)};}
        sort(E+1,E+m+1),m=unique(E+1,E+m+1)-E-1;
        ffor(i,1,m) {
            deg[E[i].first]++,deg[E[i].second]++;
            G[E[i].first].push_back(E[i].second),G[E[i].second].push_back(E[i].first);  
        }
        ffor(i,1,n) Deg[i]=deg[i];
        res=*min_element(deg+1,deg+n+1),solve(),solve(res);
        printf("%d ",(int)ot.size());for(auto id:ot) printf("%d ",id); puts("");
        ans.clear(); Solve();
        printf("%d ",(int)ans.size());for(auto pr:ans) printf("%d ",pr); puts("");
    }
    return 0;
}