CF1244D
题意
给出一个有n个节点的树,有三种颜色,给出每个节点染成三种颜色分别的代价,求一种染色方法使得任意相邻三点之间没有重复的颜色.要求输出任意一种方案,且保证代价最小.如果不存在方案,那么输出-1
$3<=n<=1e6$
$0<=c_{1i},c_{2i},c_{3i}<=1e9$
第一行给出一个n
接下来三行一行n个数,表示染色的代价
最后n-1行,每行两个节点下标,表示这两个节点相连
思路
其实这个题很简单,只是看着吓人.
我们仔细思考一下,对于一个T型节点.比如1->2 1->3 1->4那么是无论如何也不能构建出解的.
也就是二叉树是不满足的(此处不太严谨,实际上是无论怎样调整根,都只能得到二叉树的话,是不行的)(更多叉的也不行),然后说明,这个题只有链是满足题意的.
所以我们先统计一下每个节点的度,如果有节点的度超过2,那么就输出-1.
那么对于一条链改如何处理呢.
实际上也很简单,我们假设是一个1->2->..->n的链,那么如果第一个和第二个确定了,第三个也确定了,那么实际上第四个也确定了,以此类推,只要前两个确定了,那么后续的都确定了.
也就是我们枚举前两个的值即可.(或者为了方便枚举前三个也行,毕竟这个题保证了至少三个节点.)
具体的算法我们可以判断完是链之后建立一个映射关系,就让编码稍微轻松一些.
AC代码
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
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
#define maxn (int)1e6 + 10
#define ll long long
#define endl '\n'
int c[4][maxn];
int n;
int p[] = {0, 1, 2};
vector<int> ver[maxn];
int in[maxn];
int Index[maxn];
int truecol[maxn];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> c[0][i];
}
for (int i = 1; i <= n; ++i) {
cin >> c[1][i];
}
for (int i = 1; i <= n; ++i) {
cin >> c[2][i];
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
ver[u].push_back(v);
ver[v].push_back(u);
++in[u];
++in[v];
}
int s = -1;
for (int i = 1; i <= n; ++i) {
if (in[i] > 2) { // 不是链
cout << -1 << endl;
return 0;
}
if (in[i] == 1) {
s = i;
}
}
int id = 0;
Index[0] = s;
int to = ver[s][0];
int cntloop = 1;
while (cntloop < n) { // 创建映射(其实写复杂了)
++id;
Index[id] = to;
int tmp = ver[to][0];
if (tmp == Index[id - 1]) {
tmp = ver[to][1];
}
to = tmp;
++cntloop;
}
ll ans = 0ll;
ll minn = (ll)1e18;
int t0, t1, t2;
do {
ans = 0;
for (int i = 0; i < 3; ++i) {
ans += c[p[i]][Index[i]];
}
int pre = p[2], ppre = p[1];
for (int i = 3; i < n; ++i) {
int tcol = 3 - pre - ppre;
ans += c[tcol][Index[i]];
ppre = pre;
pre = tcol;
}
if (ans < minn) {
minn = ans;
t0 = p[0], t1 = p[1], t2 = p[2];
}
} while (next_permutation(p, p + 3)); // 注意拼写
cout << minn << endl;
p[0] = t0, p[1] = t1, p[2] = t2;
truecol[Index[0]] = p[0];
truecol[Index[1]] = p[1];
truecol[Index[2]] = p[2];
int pre = p[2], ppre = p[1];
for (int i = 3; i < n; ++i) {
int tcol = 3 - pre - ppre;
truecol[Index[i]] = tcol;
ppre = pre;
pre = tcol;
}
for (int i = 1; i <= n; ++i) {
cout << truecol[i] + 1 << " ";
}
cout << endl;
return 0;
}
