题目描述

https://www.luogu.com.cn/problem/P4410

题解

原图显然是一个仙人掌(似乎还有些别的性质 但是其实没什么必要)

先考虑树的情况,题意即为不能同时选择相邻的两点,设表示选/不选时,子树内的最大战斗力

在环上如何dp?

在环上找到一个点并从那里把环断开,分选或不选两种,分别进行dp来推出即可

代码

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
#include <bits/stdc++.h>
#define N 500005
using namespace std;

int n, m, ans, a[N], f[N][2];
int head[N], pre[N<<1], to[N<<1], sz;

inline void addedge(int u, int v) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

int dfn[N], low[N], stk[N], top, c[N], tot, tme;

void solve(int x) {
int a0 = 0, a1 = 0, b0 = 0, b1 = -0x3f3f3f3f; //不选x
for (int i = 1; i <= tot; i++) {
a0 = max(b0, b1) + f[c[i]][0]; a1 = b0 + f[c[i]][1];
b0 = a0; b1 = a1;
}
f[x][0] += max(b0, b1);
a0 = a1 = 0; b0 = -0x3f3f3f3f; b1 = 0; //选择x
for (int i = 1; i <= tot; i++) {
a0 = max(b0, b1) + f[c[i]][0]; a1 = b0 + f[c[i]][1];
b0 = a0; b1 = a1;
}
f[x][1] += b0;
}

void tarjan(int x) {
dfn[x] = low[x] = ++tme;
stk[++top] = x;
f[x][1] = a[x];
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
if (dfn[x] == low[y]) {
int u = 0; tot = 0;
do {
u = stk[top--];
c[++tot] = u;
} while (u != y);
solve(x);
} else if (dfn[x] < low[y]) {
f[x][0] += max(f[y][0], f[y][1]);
f[x][1] += f[y][0];
}
} else low[x] = min(low[x], dfn[y]);
}
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d %d", &u, &v);
addedge(u, v);
}
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
tarjan(1);
printf("%d\n", max(f[1][0], f[1][1]));
return 0;
}

评论