自动搬运

查看原文

来自洛谷，原作者为

	happy_dengziyue GD OIer|路漫漫其修远兮，吾将上下而求索

搬运于2025-08-24 22:29:47，当前版本为作者最后更新于2021-10-06 17:40:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1 思路

注：本题的解法正确性并未得到证明，但是能过。

我们一看题目，发现题目还有重点突出每个点最多和 $7$ 个点相邻。那么，我们就可以知道，最复杂最可能无解的图，就是 $8$ 个点的完全图。

然鹅，哪怕是这样，都有解，即样例。

所以我们可以得出结论：没有无解的情况。可能是因为 小 B 的孝心感天动地。

那么怎么构造呢？深搜是明显不行的。我们可以使用一种奇技淫巧。

首先，将颜色编号为 $0-3$，然后，找出所有不满足要求的点，加入队列。

每次从队首取一个点。如果这个点已经满足要求就不去动它，否则，将它的颜色改成所有与它直接相连的点的中最稀有的颜色。

依据容斥原理，我们可以证明，这个颜色在周围只有 $1$ 个或者 $0$ 个点拥有。

当然了，改完颜色后，又要判断所有与之相连的点有哪个或哪些不满足要求，压入队列。

队列为空时，答案就出来了。

2 代码与记录

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define max_n 25000//最大点数
#define max_m 200000//最大边数
int t;//测试数据组数
int n;//点数
int m;//边数
struct E{
	int v,nx;
}e[max_m+2];//边
int ei;//下标
int fir[max_n+2];//开始路径
int micnt,micol;//周围最少的颜色的数量与那个颜色
int col[max_n+2];//颜色
queue<int>q;//队列
inline void addedge(int u,int v){
	e[++ei]=(E){v,fir[u]}; fir[u]=ei;
}
int asksame(int u,int x){
	int res=0;
	for(int i=fir[u];i;i=e[i].nx){
		if(x==col[e[i].v])++res;
	}
	return res;//在点u周围有res个颜色为x的点
}
inline int mi(int a,int b){
	return a<b?a:b;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("P7428_1.in","r",stdin);
	freopen("P7428_1.out","w",stdout);
	#endif
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		ei=0;
		memset(fir,0,sizeof(fir));
		for(int i=1,u,v;i<=m;++i){
			scanf("%d%d",&u,&v);
			addedge(u,v);
			addedge(v,u);
		}
		memset(col,0,sizeof(col));
		while(!q.empty())q.pop();
		for(int i=1;i<=n;++i){
			if(asksame(i,col[i])>1)q.push(i);
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			if(asksame(u,col[u])<=1)continue;
			micnt=8;
			for(int i=0,k;i<4;++i){
				k=asksame(u,i);
				if(k<micnt){
					micnt=k;
					micol=i;
				}
			}
			col[u]=micol;//此时必定有micnt<=1
			for(int i=fir[u],v;i;i=e[i].nx){
				v=e[i].v;
				if(col[v]==micol&&asksame(v,micol)>1)q.push(v);
			}
		}
		for(int i=1;i<=n;++i)putchar(col[i]+'a');
		puts("");
	}
	return 0;
}

记录传送门

By dengziyue