codeforces-Ed87-E

codeforces-Ed87-E

七月 08, 2020

E. Graph Coloring

题意
有一个n个点m条边的无自环无向图
要求给每个点分别赋值 val=1,2,3;
存在以下限制
val=1,2,3的点分别不能超过n1,n2,n3 (n1+n2+n3==n)
且相邻两点的val差的绝对值=1
问是否能给这些点赋值且满足要求
n=5000，m=1e5

首先对于一个联通的子图 它可以被黑白染色成两部分
一部分赋值为2剩下的则为1和3

其次考虑所有子图构成的图
利用背包求解每个子图中是黑色赋值为2还是白色赋值为2
bool dp[i][j]表示对于前i个子图 有j个点赋值为2 时是否存在可行方案
初始化dp [0][0] =1
int co i j 表示第j个子图中i(1/2)色有多少个点
那么前i个子图中有j+co[1/2][i]个点赋值为2时是否可行 dp i j+co[1/2][i] | = dp [i-1][j]以01背包形式转移
那么最后若 dp 总子图数 n2 ==1则存在解
可以根据 dp 总子图数 n2 逆向路径还原 若dp [i-1][j]-co[1/2][i] 有前继值那么一定可以追溯到 dp [0][0] ,
若dp [i-1][j]-co[1/2][i]均有则任选其中一条路径
用mk记录对于第i个子图是子图中染成白色赋值为2还是黑色赋值为2
最后输出答案

(转自某博客)

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
# include <bits/stdc++.h>

using namespace std;

//Start
typedef long long ll;
typedef double db;

# define mp(a,b) make_pair(a,b)

# define x(a) a.first

# define y(a) a.second

# define b(a) a.begin()

# define e(a) a.end()

# define sz(a) int((a).size())

# define pb(a) push_back(a)

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

//Data
const int N=5e3,M=1e5;
vector<int> e[N+7];
int f[N+7][N+7],mk[N+7];

//Dfs
int d[N+7],ct[N+7],co[3][N+7];
void Dfs(int u,int t,int cn){
	d[u]=t,ct[u]=cn,co[t][cn]++;
	for(int v:e[u])
		if(!d[v]) Dfs(v,3-t,cn); //二分图染色
		else if(d[u]+d[v]!=3) puts("NO"),exit(0); //不是二分图
}

//Main
int main(){
	int n,m; scanf("%d%d",&n,&m);
	int a,b,c; scanf("%d%d%d",&a,&b,&c);
	for(int i=1;i<=m;i++){
		int u,v; scanf("%d%d",&u,&v);
		e[u].pb(v),e[v].pb(u);
	}
	int w=0;
	f[0][0]=1;
	for(int i=1;i<=n;i++)if(!d[i]){
		Dfs(i,1,++w); 
		for(int j=n;j>=0;j--){
			if(j+co[1][w]<=n&&f[w-1][j]) f[w][j+co[1][w]]=1;
			if(j+co[2][w]<=n&&f[w-1][j]) f[w][j+co[2][w]]=1; // 分组背包
		}
	}
	if(!f[w][b]) return puts("NO"),0;
	else puts("YES");
	for(int i=w,j=b;i>=1;i--){
		if(j-co[1][i]>=0&&f[i-1][j-co[1][i]]) mk[i]=1,j-=co[1][i];
		else if(j-co[2][i]>=0&&f[i-1][j-co[2][i]]) mk[i]=2,j-=co[2][i]; //回溯
		//if(j-co[1][i]>=0&&f[i-1][j-co[1][i]]) mk[i]=1,j-=co[1][i];
		//if(j-co[2][i]>=0&&f[i-1][j-co[2][i]]) mk[i]=2,j-=co[2][i]; 
		/*
		原来是这么写的，没想到前面j-=co[1][i]会影响这里！！！
		*/
	}
	for(int i=1;i<=n;i++)
		if(mk[ct[i]]==1){
			if(d[i]==1) printf("2");
			else {
				if(a) printf("1"),a--;
				else printf("3");				
			}
		} else {
			if(d[i]==2) printf("2");
			else {
				if(a) printf("1"),a--;
				else printf("3");				
			}
		}
	puts("");
	return 0;
}