题面
现有一个 $n$ 个点 $m$ 条边的无向图，要求用 ${1,2,3}$ 对每个点染色，使得相邻的两个点的权值的绝对值之差刚好为 $1$。现在需要求出任意一个方案，使得一共染了 $n_1$ 个 $1$，$n_2$ 个 $2$，$n_3$ 个 $3$。保证 $n_1+n_2+n_3=n$。
无解输出 NO。
有解输出一行 YES，并在下一行输出一个字符串，第 $i$ 位表示点 $i$ 的颜色。
$1 \leq n \leq 5 \times 10^3$, $0 \leq m \leq 10^5$
题解
首先，如果有奇环显然无解。
多手推几次可以发现，$1,3$ 可以互换位置，$2$ 必定间隔出现。
所以可以进行二分图染色。
每个联通块中，必定有黑色全为 $2$，白色全为 $1,3$ ；或黑色全为 $1,3$，白色全为 $2$。
因此可以跑个背包来判断是否能恰好组合出 $n_2$，并逆推出方案，然后将这些点染成 $2$，其他点随意染成 $1,3$ 即可。
实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
struct edge{
int to,nxt;
}ed[101010*2];int edcnt=0;
int hd[5050];
inline void adde(int u,int v){
ed[++edcnt].to=v;
ed[edcnt].nxt=hd[u];
hd[u]=edcnt;
}
/*
blk[i] - i号点所在联通块
col[i] - i号点黑白染色的颜色
ans[i] - i号点答案中的颜色
*/
int ni[4],blk[5050],vis[5050],col[5050],ans[5050];
vector<int> blkin[5050];
int cnt[5050][2],dp[5050][5050];
bool dfs(int blkid,int u,int fa){
if(vis[u]){
if(col[u]!=!col[fa]) return true;
return false;
}
blk[u]=blkid;
blkin[blkid].push_back(u);
vis[u]=1;
col[u]=!col[fa];
cnt[blkid][col[u]]++;
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(dfs(blkid,v,u)) return true;
}
return false;
}
int totblk=0;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=3;++i)scanf("%d",&ni[i]);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
for(int i=1;i<=n;++i){
if(blk[i])continue;
if(dfs(++totblk,i,i)){
puts("NO");
return 0;
}
}
//背包 似乎可以用翻转的思路来降到一维
dp[0][0]=1;
for(int i=1;i<=totblk;++i){
for(int j=n;j>=0;--j){
if(j-cnt[i][0]>=0 && dp[i-1][j-cnt[i][0]])
dp[i][j]=1;
if(j-cnt[i][1]>=0 && dp[i-1][j-cnt[i][1]])
dp[i][j]=1;
}
}
int left=ni[2];
if(!dp[totblk][left]){
puts("NO");
return 0;
}
//逆推方案并染色
for(int i=totblk;i>=1;--i){
if(cnt[i][0] <= left && dp[i-1][left-cnt[i][0]]){
for(int v:blkin[i])
if(col[v]==0)ans[v]=2,left--;
}else{
for(int v:blkin[i])
if(col[v]==1)ans[v]=2,left--;
}
}
for(int i=1;i<=n;++i){
if(ans[i]) continue;
if(ni[1]){
ans[i]=1;
ni[1]--;
}else ans[i]=3;
}
puts("YES");
for(int i=1;i<=n;++i)printf("%d",ans[i]);
}