目录
显示
题目链接
https://www.luogu.com.cn/problem/P5361
题解
两个问题能放在一道题里,说明这两个问题间应该存在点内在联系。
我们先看第一问。
第一问比较简单,我们每次从图上删除度数最小的点,并更新答案,即可确保 \(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; }