[BZOJ 1040][ZJOI 2008] 骑士

题目大意

有 $n$ 个骑士,每个骑士有一个战斗力值 $a_i$,同时每个骑士有一个讨厌的骑士。现从中选出一堆骑士使得战斗力和最大,同时一个骑士不能与他讨厌的骑士都被选,求最大战斗力和。

$1 \leqslant n \leqslant 1,000,000$

$1 \leqslant a_i \leqslant 1,000,000$

题目链接

BZOJ 1040

CodeVS 1423

题解

讨厌关系其实是双向的,所以以讨厌关系建图,将得到一个环套树森林。考虑每一棵环套树,用 dfs 找到环,随便选环上的一条边断开,分别以边两边的节点为根跑树形 DP,取让根节点不被选择的值更新答案(这样可以保证它与被断开的边那头的点不同时被选)。

树形 DP 部分比较显然:

以下是吐槽部分:

我写这道题时脑子似乎进水了。。。

先是读数时每个骑士少读一个数,再是 dfs 时 banned 前少了引用,更傻的是 DBG 时写成了 #define BDG,以上三个错误每一个各找了半个小时。。。

代码

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
#include <cstdio>
#include <algorithm>
// #define DBG
const int MAXN = 1000005;
struct Edge;
struct Node {
Edge *e;
int val;
long long f[2];
bool vis;
#ifdef DBG
int id;
#endif
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next, *rev;
Edge() {}
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
};
void addEdge(int u, int v) {
N[u].e = new Edge(&N[u], &N[v]);
N[v].e = new Edge(&N[v], &N[u]);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
int n;
void dfs(Node *u, Edge *last, Node *&n1, Node *&n2, Edge *&banned) {
#ifdef DBG
printf("dfs(%d)\n", u->id);
#endif
u->vis = true;
for (Edge *e = u->e; e; e = e->next) {
if (e->rev == last) continue;
if (e->v->vis) {
n1 = u;
n2 = e->v;
banned = e;
#ifdef DBG
printf("get n1 = %d, n2 = %d\n", n1->id, n2->id);
printf("banned:(%d, %d)\n", banned->u->id, banned->v->id);
#endif
continue;
}
dfs(e->v, e, n1, n2, banned);
}
}
void dp(Node *u, Edge *banned, Edge *last = NULL) {
#ifdef DBG
printf("dp(%d)\n", u->id);
printf("banned:(%d, %d)\n", banned->u->id, banned->v->id);
#endif
u->f[0] = 0;
u->f[1] = u->val;
for (Edge *e = u->e; e; e = e->next) {
if (e == banned || e->rev == banned || e->rev == last) continue;
dp(e->v, banned, e);
u->f[1] += e->v->f[0];
u->f[0] += std::max(e->v->f[0], e->v->f[1]);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, v;
scanf("%d %d", &x, &v);
N[i].val = x;
addEdge(v, i);
#ifdef DBG
N[i].id = i;
#endif
}
Node *n1, *n2;
Edge *banned;
long long ans = 0;
for (int i = 1; i <= n; i++) if (!N[i].vis) {
dfs(&N[i], NULL, n1, n2, banned);
dp(n1, banned);
long long temp = n1->f[0];
dp(n2, banned);
ans += std::max(temp, n2->f[0]);
}
printf("%lld\n", ans);
return 0;
}