E. Graph Coloring
You are given an undirected graph without self-loops or multiple edges which consists of n vertices and m edges. Also you are given three integers n1, n2 and n3.
Can you label each vertex with one of three numbers 1, 2 or 3 in such way, that:
Each vertex should be labeled by exactly one number 1, 2 or 3; The total number of vertices with label 1 should be equal to n1; The total number of vertices with label 2 should be equal to n2; The total number of vertices with label 3 should be equal to n3; |colu−colv|=1 for each edge (u,v), where colx is the label of vertex x. If there are multiple valid labelings, print any of them.
Input
The first line contains two integers n and m (1≤n≤5000; 0≤m≤105) — the number of vertices and edges in the graph.
The second line contains three integers n1, n2 and n3 (0≤n1,n2,n3≤n) — the number of labels 1, 2 and 3, respectively. It’s guaranteed that n1+n2+n3=n.
Next m lines contan description of edges: the i-th line contains two integers ui, vi (1≤ui,vi≤n; ui≠vi) — the vertices the i-th edge connects. It’s guaranteed that the graph doesn’t contain self-loops or multiple edges.
Output
If valid labeling exists then print “YES” (without quotes) in the first line. In the second line print string of length n consisting of 1, 2 and 3. The i-th letter should be equal to the label of the i-th vertex.
If there is no valid labeling, print “NO” (without quotes).
Examples
input
6 3
2 2 2
3 1
5 4
2 5
output
YES
112323
input
5 9
0 2 3
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
output
NO
解题思路：
一个图，不一定连通，且可能存在环（非自环）。用1，2，3三种颜色给点染色。 要求1，2，3数量分别是n1,n2,n3且 相邻两点 差的绝对值为1，也就是同一个颜色不能相邻。 1，3不能相邻。
因为1，3不能相邻，所以本质上，可以把颜色看成两种，因为一旦确定了2，剩下的1，3随便分。
第一步： 先找出所有的连通块，并且算出每个连通块，染成颜色1和颜色2的数量。这里的颜色是暂时的。不代表最终的颜色。 如果一个连通块中，有大小为偶数的环，那么必然会存在颜色相邻的情况。直接输出 NO 。 第二步： 要看看，这些连通块的1，2 的数量，能不能凑出正好等于n2。（这里比赛的时候没有想出来，比赛想的dfs但是显然超时了）。 还是DP大法好。dp[i][j]表示前i个连通块 能不能凑出 j 来。用 0 ， 1 表示。 那么显然 dp[cnt][n2] == 1 的话说明可以凑出来。然后就回溯。 第三步： 回溯。因为前面是用dps数组从0凑到n2的。那么现在往回推就从n2推到0.因为可以顺着推过来，那么反着回去肯定是可行的。然后判断一下，这个连通块是 原来颜色1的染成2 还是原来颜色2的染成2就行了。 最后剩下的点就1，3随便分就行了。
AC代码：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std
;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
typedef pair
<int,int> PII
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double ld
;
const int MOD
= 1e9 + 7;
const ll mod
= 10007;
const double eps
= 1e-9;
const ll INF
= 0x3f3f3f3f3f3f3f3fll;
inline int read(){int ret
= 0, sgn
= 1;char ch
= getchar();
while(ch
< '0' || ch
> '9'){if(ch
== '-')sgn
= -1;ch
= getchar();}
while (ch
>= '0' && ch
<= '9'){ret
= ret
*10 + ch
- '0';ch
= getchar();}
return ret
*sgn
;}
inline void Out(int a
){if(a
>9) Out(a
/10);putchar(a
%10+'0');}
int qpow(int m
, int k
, int mod
){int res
=1%mod
,t
=m
%mod
;while(k
){if(k
&1)res
=res
*t
%mod
;t
=t
*t
%mod
;k
>>=1;}return res
;}
ll
gcd(ll a
,ll b
){if(b
> a
) swap(a
,b
); return b
==0?a
: gcd(b
,a
%b
);}
ll
lcm(ll a
,ll b
){return a
/gcd(a
,b
)*b
;}
ll
inv(ll x
,ll mod
){return qpow(x
,mod
-2,mod
)%mod
;}
int t
= 1,cas
= 1;
int n
,m
;
const int N
= 5e3+3;
typedef long long ll
;
vector
<int> G
[N
];
int cnt
[2];
int color
[N
];
int mark
[N
];
int a
,b
,c
;
int tt
= 0;
int flag
= 1;
void dfs(int pos
,int par
,int x
){
if(color
[pos
] != -1) return;
cnt
[x
] ++;
color
[pos
] = x
;
mark
[pos
] = tt
;
int nn
= G
[pos
].size();
for(int i
= 0;i
< nn
;i
++)
{
int to
= G
[pos
][i
];
if(flag
&& par
!= to
){
if(color
[to
] == color
[pos
])
{
flag
= 0;
return ;
}
dfs(to
,pos
,x
^1);
}
}
}
void dfs2(int pos
,int par
,int x
,int id
){
if(color
[pos
] == 2) return;
if(color
[pos
] == x
)
color
[pos
] = 2;
int nn
= G
[pos
].size();
for(int i
= 0;i
< nn
;i
++)
{
int to
= G
[pos
][i
];
if(par
!= to
){
dfs2(to
,pos
,x
,id
);
}
}
}
int vt
[5005][2];
int dp
[5005][5005];
int id
[5005];
signed main()
{
while(t
--)
{
memset(color
,-1,sizeof(color
));
memset(mark
,-1,sizeof(mark
));
int a
,b
,c
;
cin
>>n
>>m
; cin
>>a
>>b
>>c
;
for(int i
= 0; i
< m
; i
++){
int x
,y
;
cin
>>x
>>y
;
x
--;y
--;
G
[x
].pb(y
);
G
[y
].pb(x
);
}
for(int i
= 0 ; i
< n
; i
++){
cnt
[0] = cnt
[1] = 0;
if(flag
&& color
[i
] == -1){
dfs(i
,-1,0);
id
[tt
] = i
;
vt
[tt
][0] = cnt
[0];
vt
[tt
][1] = cnt
[1];
tt
++;
}
}
dp
[0][0] = 1;
for(int i
= 0 ; i
< tt
;i
++){
int x
= vt
[i
][0];
int y
= vt
[i
][1];
for(int j
= 0 ; j
<= b
; j
++){
if(dp
[i
][j
]){
if(j
+x
<= b
) dp
[i
+1][j
+x
] = 1;
if(j
+y
<= b
) dp
[i
+1][j
+y
] = 1;
}
}
}
if(flag
&& dp
[tt
][b
]){
cout
<<"YES"<<endl
;
int tmp
= b
;
for(int i
= tt
; i
>= 1; i
--){
int x
= vt
[i
-1][0];
int y
= vt
[i
-1][1];
if(dp
[i
-1][tmp
-x
]){
tmp
-= x
;
dfs2(id
[i
-1],-1,0,i
-1);
}
else if(dp
[i
-1][tmp
-y
]){
tmp
-= y
;
dfs2(id
[i
-1],-1,1,i
-1);
}
else{
cout
<<"hahahaha"<<endl
;
return 0;
}
}
for(int i
= 0 ; i
< n
; i
++) {
if(color
[i
] == 2) cout
<<2;
else{
if(a
){a
--;cout
<<1;}
else cout
<<3;
}
}
}
else
cout
<<"NO"<<endl
;
}
}
