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; }
上一篇: 茶叶的原产地在中国,那么形成了怎样相应的饮茶礼仪?
下一篇: 荤菜和素菜的区别,你真的知道吗