题解 CF1354E 【Graph Coloring】

## 题目大意 $n$个节点$m$条边的无向图，要求用$\{1,2,3\}$对每个点染色，使得相邻的两个点的权值差**刚好**为$1$。现在需要求出一个方案，使得一共染了$n_1$个$1$,$n_2$个$2$,$n_3$个$3$。无解输出$\rm NO$。 ## 题解 观察$1,3$的性质，我们能够发现： - $1,3$都只能和$2$相邻 - $1,3$不能和自己与对方相邻 那么，假设我们把所有的$3$都当作$1$，可以保证图的性质不变，且$2$的个数不变。这样，原图就变成了一个二分图染色问题。 但是到这里还没有结束。$1,3$可以相互转换，因此可以很方便地处理$n_1,n_3$的限制；但是我们需要**恰好**染了$n_2$个$2$，就得综合考虑每一个二分图应该怎么样染颜色$2$。 事实上，这是一个背包问题。每张二分图染$2$的数量，只有两种情况。假设这张二分图左边的节点数为$a$，右边的为$b$，那么我们可以染$a$或$b$个$2$。于是，我们可以**默认将所有染色图右边染色**，然后考虑哪些二分图需要翻转颜色。这样的好处是，我们将$a,b$中二选一的问题变成了是否选择$a-b$的$01$背包问题。 还需要注意的是，如果要用滚动数组优化，$a-b$可能是负数。因此需要根据情况改变枚举的方向。 ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } const int MAXN =5e3+3,MAXM=1e5+3; int head[MAXN],ver[MAXM*2],nxt[MAXM*2],tot; void add(int u,int v){ ver[++tot]=v,nxt[tot]=head[u],head[u]=tot; } int n,m,cnt,one[MAXN],two[MAXN],del[MAXN],n1,n2,n3; int col[MAXN],id[MAXN],_dp[MAXN*2],*dp; bool rev[MAXN]; void dfs(int u){ if(col[u]==2) ++two[id[u]]; else ++one[id[u]]; for(int i=head[u];i;i=nxt[i]){ int v=ver[i]; if(!col[v]) col[v]=3-col[u],id[v]=id[u],dfs(v); else if(col[v]==col[u]) puts("NO"),exit(0); } } int main(){ n=qread(),m=qread(),dp=_dp+n; n1=qread(),n2=qread(),n3=qread(); up(1,m,i){ int u=qread(),v=qread(); add(u,v),add(v,u); } up(1,n,i) if(!col[i]) col[i]=1,id[i]=++cnt,dfs(i),n2-=two[cnt]; if(n2==0){ puts("YES"); up(1,n,i){ if(rev[id[i]]) col[i]=3-col[i]; if(col[i]==2) putchar('2'); else{ if(n1) putchar('1'),--n1; else putchar('3'); } } return 0; } up(1,cnt,i){ del[i]=one[i]-two[i]; int s=del[i]; if(s>0) {dn(n,-n,j) if(dp[j]&&!dp[j+s]) dp[j+s]=i;} else {up(-n,n,j) if(dp[j]&&!dp[j+s]) dp[j+s]=i;} if(!dp[s]) dp[s]=i; } if(!dp[n2]) puts("NO"),exit(0); puts("YES"); for(int p=n2;p;p=p-del[dp[p]]) rev[dp[p]]=true; up(1,n,i){ if(rev[id[i]]) col[i]=3-col[i]; if(col[i]==2) putchar('2'); else{ if(n1) putchar('1'),--n1; else putchar('3'); } } return 0; } ```