2021牛客暑期多校训练营8 C题: Fuzzy Graph

C题: Fuzzy Graph

原题链接:https://ac.nowcoder.com/acm/contest/11259/C

题目大意

有一张 $n(3\le n\le 3\cdot 10^5)$ 个点 $m(3\le m\le 5\cdot 10^5)$ 条边的简单无向图(保证初始连通)，需要将每个顶点染为红绿蓝三种颜色之一。然后对于每条边，若其两个端点颜色一样，则边也变成对应颜色，否则保持黑色。
基础目标:

• 仅有黑边的情况下，图依旧保持连通。

在完成基础目标的前提下，还可以完成以下额外目标:

1. 每种颜色的顶点数相同，保证 $n$ 是 $3$ 的倍数。
2. 某种颜色的顶点数量最多，但该颜色的节点的相邻边都是黑色。这个额外目标可以达成多次。

如下所示，左图是染色前，右图是按某种方式染色后的结果，其满足基础目标，每种颜色的顶点数相同，绿色节点的出现次数最多且相邻边均为黑色，因此满足两个额外条件。
(图片摘自原题)

给定未染色的图，求至少完成一个额外目标的方案，或判断无解。

题解

首先考虑基础目标，我们可以将原图删去一些边，使得剩下的{V,E}构成一棵树，然后保证树上相邻的点都为异色即可。
我们以任意点为跟跑出一棵Tarjan树，然后按红绿相间的方式对整张图进行初步染色，现在我们完成了基础目标。
然后考虑额外目标:

1. 若当前的红/绿点数均大于 $\frac{n}{3}$ (即对于额外目标1而言，目前点数都是过量的)，我们可以考虑将 $\frac{n}{3}$ 个点转化为蓝色，使得三种颜色的点数相等(操作过程中可以从根向下递归，然后优先选取叶节点/较深的点进行颜色转换(较深的修改通常对其他点造成的影响较小)，注意判断相邻即可);
2. 若红/绿点数有一者少于 $\frac{n}{3}$ (即另一颜色点数多于 $\frac{2n}{3}$ )，则我们考虑额外目标2，我们设 $M$ 表示点数较多的颜色， $L$ 表示点数较少的颜色，则我们有 $M_{叶节点数}+M_{非叶节点数}>\frac{2n}{3},L_{叶节点数}+L_{非叶节点数}<\frac{n}{3}$ ，因为每个非叶节点都至少有一个异色的子节点，所以我们有结论 $M_{非叶节点数}<=L_{叶节点数}+L_{非叶节点数}<\frac{n}{3}$ ，所以 $M_{叶节点数}>\frac{n}{3}$ ，总叶节点数也应大于 $\frac{n}{3}$ ，那么我们将所有叶节点染成蓝色，即可使得蓝色点数最多，且蓝色节点形成一个独立集，额外目标2完成;

根据以上策略与题目的数据限制，可以保证不会出现无解的情况(没有1.和2.以外的情况)。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define For(i,n,m) for(int i=n;i<=m;i++)
#define FOR(i,n,m) for(int i=n;i>=m;i--)
using namespace std;
void read(int &x){
	int ret=0;
	char c=getchar(),last=' ';
	while(!isdigit(c))last=c,c=getchar();
	while(isdigit(c))ret=ret*10+c-'0',c=getchar();
	x=last=='-'?-ret:ret;
}

const int MAXN=3e5+5;
int T,n,m,r,g,vis[MAXN],leaf[MAXN];//r记录红色点数,g记录绿色点数,vis记录颜色(1红0绿2蓝),leaf标记是否为叶节点
vector<int>e[MAXN],dfe[MAXN];//e记录图边,dfe记录Tarjan跑dfs过程中得到的树边

void Tarjan(int x,int fa,int c){
	if(c)r++;//c为1染红色,增加红色计数
	else g++;//c为0染绿色,增加绿色计数
	vis[x]=c;//颜色标记
	int son;
	bool isleaf=true;//标记是否为Tarjan树中的叶节点
	For(i,0,e[x].size()-1){
		son=e[x][i];
		if(~vis[son])continue;//若不是-1,即已访问过,则跳过回边
		Tarjan(son,x,c^1);//先进行递归,注意c^1间接染色
		dfe[x].push_back(son);//存入树边
		isleaf=false;//若有子节点,则非叶节点
	}
	leaf[x]=isleaf?1:0;//标记是否为叶节点
}

void paint(int x){
	if(dfe[x].empty()){//叶节点
		if(vis[x]==1){//原颜色为红
			if(r>n/3)r--,vis[x]=2;//若红色点数仍超量,染色为蓝色
		}
		else{//原颜色为绿
			if(g>n/3)g--,vis[x]=2;//若绿色点数仍超量,染色为蓝色
		}
		return;
	}
	int son;
	bool f=true;//标记非叶节点是否可染色为蓝色
	For(i,0,dfe[x].size()-1){
		son=dfe[x][i];
		paint(son);//先递归染色较深的节点
		if(vis[son]==2)f=false;//若有子节点已经染色为蓝色,则该节点不可再染色
	}
	if(f){//可染色
		if(vis[x]==1){//原颜色为红
			if(r>n/3)r--,vis[x]=2;//若红色点数仍超量,染色为蓝色
		}
		else{//原颜色为绿
			if(g>n/3)g--,vis[x]=2;//若绿色点数仍超量,染色为蓝色
		}
	}
}

int main()
{
	read(T);
	while(T--){
		read(n),read(m);
		int u,v;
		memset(vis,-1,sizeof(vis));//初始化颜色标记为-1
		For(i,1,n)e[i].clear(),dfe[i].clear();//清空边
		while(m--){
			read(u),read(v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		r=g=0;//清空颜色计数
		Tarjan(1,-1,1);
		if(r<=n/3*2&&g<=n/3*2){//选择额外目标1
			paint(1);//染色使得各颜色点数相等
			For(i,1,n)printf("%c",vis[i]==1?'R':(vis[i]==0?'G':'B'));
			puts("");
		}
		else{//选择额外目标2
			For(i,1,n)if(leaf[i])vis[i]=2;//将全部叶节点染色为蓝色,使得蓝点形成独立集且大小最大
			For(i,1,n)printf("%c",vis[i]==1?'R':(vis[i]==0?'G':'B'));
			puts("");
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88