【题解】CF1354E

Link
一些性质转化加一个简单 dp，感觉是 CF 很喜欢出的套路题（

我们观察一下连边的条件，发现能连的边只有 $1-2$ 和 $2-3$ 。也就是说 $1$ 和 $3$ 并没有区别，于是把 $1$ 和 $3$ 看作同一个颜色。

然后很自然的想到黑白染色，注意要判断有没有颜色冲突。

黑白染色之后，对于每一个连通块，我们得到了其中黑色和白色的个数。显然，要么一个连通块里的黑色点全部染成颜色 $2$ ，白色点染成 $1$ 和 $3$；要么白色点全部染成颜色 $2$ ，黑色点染成 $1$ 和 $3$。

现在我们想要知道把哪些点染成 $2$，哪些点染成 $1$ 或 $3$。于是做一个 $n^2$ 的 dp。和 $01$ 背包一样（好像不太一样 不管了x），设 $dp_{i.j}$ 表示前 $i$ 个连通块中，是否可能染 $j$ 个颜色 $2$。转移也和 $01$ 背包没有太大差异，不再赘述。

最后统计答案的时候按照背包出来的方案分一下，再随意分配一下 $1$ 和 $3$，输出答案。

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int MAXN=5005;
int n,m;
vector<int> v[MAXN];
int n1,n2,n3;
int cnt[MAXN],total=0;
int c1[MAXN];
bool vis[MAXN];
bool dp[MAXN][MAXN];
int la[MAXN];
bool color[MAXN];
bool flag=true;
int head[MAXN];

void dfs(int p,bool t){
	vis[p]=true;
	c1[total]+=t;
	cnt[total]++;
	color[p]=t;
	for (int i:v[p]){
		if (!vis[i]) dfs(i,t^1);
		else if (color[i]!=(t^1)){
			flag=false;
			return;
		}
	}
}

void coloring(int p,bool t){
	color[p]=t;
	vis[p]=true;
	for (int i:v[p])
		if (!vis[i]) coloring(i,t^1);
}

int main()

{
	cin>>n>>m;
	cin>>n1>>n2>>n3;
	for (int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i=1;i<=n;i++){
		if (!vis[i]){
			total++;
			head[total]=i;
			dfs(i,true);
			if (!flag){
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}

	dp[0][0]=true;
	for (int i=1;i<=total;i++){
		for (int j=n2;j>=0;j--){
			if (j-c1[i]>=0 && dp[i-1][j-c1[i]])
				dp[i][j]=true;

			int tmp=cnt[i]-c1[i];
			if (j-tmp>=0 && dp[i-1][j-tmp])
				dp[i][j]=true;
		}
	}

	if (!dp[total][n2]){
		cout<<"NO"<<endl;
		return 0;
	}

	cout<<"YES"<<endl;

	memset(vis,false,sizeof(vis));
	memset(color,false,sizeof(color));
	int pos=n2,i=total;
	while (pos>0 && i>0){
		if (pos-c1[i]>=0 && dp[i-1][pos-c1[i]]){
			coloring(head[i],true);
			pos-=c1[i];
		}
		else{
			coloring(head[i],false);
			pos-=(cnt[i]-c1[i]);
		}
		i--;
	}
	
	int xcnt=0;
	for (int i=1;i<=n;i++){
		if (color[i]) cout<<2;
		else{
			if (xcnt<n1){
				cout<<1;
				xcnt++;
			}
			else cout<<3;
		}
	}

	cout<<endl;
	return 0;
}