Java教程

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

本文主要是介绍[SDOI2019] 热闹的聚会与尴尬的聚会，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

在洛谷题解逛了一圈，不是随机化乱搞就是带log的做法，这里来一个线性且正确性有保证的做法。

人傻常数大，打不过随机化/kk

题目

洛谷

LibreOJ

讲解

做法是每次删除度最小的点，贪心加入独立集。因为很多题解都证过了，这里就不证正确性了。

讲一下实现。

我们对每个点按度数桶排，然后可以从小到大枚举 \(p\)，每次删除度数不超过 \(p\) 的点并且动态更新度数，度数如果减小到删除条件就直接删掉，可以递归实现。

在删除过程中同样可以维护独立集，值得注意的是打独立集的 tag 的时候要先打再递归去删数，不然会出问题。

卡常技巧是不用 vector 而是用链表。

具体实现可以看代码。

代码

//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std; 

typedef long long LL;
const int MAXN = 10005;
int n,m;

char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

int head[MAXN],tot,deg[MAXN],hd[MAXN];
struct edge{
	int v,nxt;
}e[MAXN*45];
void Add_Edge(int u,int v){
	e[++tot] = edge{v,head[u]};
	head[u] = tot;
}
void Add_Double_Edge(int u,int v){
	Add_Edge(u,v);
	Add_Edge(v,u);
	++deg[u]; ++deg[v];
}
bool used[MAXN],del[MAXN];
int ans1[MAXN],ans2[MAXN],t1,t2,MAX;
void clr(int x,int p){
	del[x] = 1; ans1[++t1] = x;
	bool sg = 0;
	if(!used[x]) ans2[++t2] = x,used[x] = sg = 1;
	if(sg) for(int i = head[x]; i ;i = e[i].nxt) used[e[i].v] = 1;//先打tag
	for(int i = head[x],v; i ;i = e[i].nxt) {//后删数字
		if(del[v = e[i].v]) continue;
		--deg[v];
		if(deg[v] <= p) clr(v,p);
		else e[++tot] = edge{v,hd[deg[v]]},hd[deg[v]] = tot;
	}
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	for(int T = Read(); T ;-- T){
		n = Read(); m = Read(); t1 = t2 = tot = MAX = 0;
		for(int i = 0;i <= n;++ i) head[i] = deg[i] = hd[i] = used[i] = del[i] = 0;
		for(int i = 1;i <= m;++ i) Add_Double_Edge(Read(),Read());
		for(int i = 1;i <= n;++ i) e[++tot] = edge{i,hd[deg[i]]},hd[deg[i]] = tot;
		for(int p = 0;p < n;++ p){
			for(int i = hd[p]; i ;i = e[i].nxt){
				int x = e[i].v; 
				if(del[x]) continue;
				if(p > MAX) MAX = p,t1 = 0; clr(x,p);
			}
		}
		Put(t1,' ');
		for(int i = 1;i <= t1;++ i) Put(ans1[i],' '); putchar('\n');
		Put(t2,' ');
		for(int i = 1;i <= t2;++ i) Put(ans2[i],' '); putchar('\n');
	}
	return 0;
}
这篇关于[SDOI2019] 热闹的聚会与尴尬的聚会的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航