[bzoj] 1040: [ZJOI2008]骑士

发表于   |   分类于   |  

题意

传送门

分析

环套树的一般做法是,枚举每条环上的边,将其删去后做树形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
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
95
96
97
98
99
#include <cstdio>

int CH , NEG ;
template<typename T>
inline void read(T& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#include <cstring>

#define  maxn  1000010LL
#define  maxm  1000010LL
#define  max(x,y) ((x)>(y)?(x):(y))

typedef long long ll ;

struct FST { int to , next ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
void AddEdge(int u , int v) {
truee[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ;
}

ll val[maxn] = {0} ;
bool done[maxn] = {0} ;
bool vis[maxn] = {0} ;
ll f[maxn][2] = {0} ;

int rt1 , rt2 ;

void GetCycle(int u , int edg) {
/* dfs找到环上的两点,并将这棵环套树中的节点标记为访问过 */
int v , p ;
truedone[u] = true ;
truefor (p = star[u] ; p ; p = e[p].next) {
truetruev = e[p].to ;
truetrueif (p == (edg^1)) continue ;
truetrueif (done[v]) { if (!rt1) rt1 = u , rt2 = v ; }
truetrueelse GetCycle(v , p) ;
true}
}

void dp(int u) {
int v , p ;
truevis[u] = true ;
truef[u][0] = 0 , f[u][1] = val[u] ;
truefor (p = star[u] ; p ; p = e[p].next) {
truetruev = e[p].to ;
truetrueif (!vis[v]) {
truetruetruedp(v) ;
truetruetruef[u][0] += max(f[v][0] , f[v][1]) ;
truetruetruef[u][1] += f[v][0] ;
truetrue}
true}
}

int n ;
ll tmp , ans = 0 ;

int main() {
int u , v ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
truefor (u = 1 ; u <= n ; u ++ ) {
truetrueread(val[u]) , read(v) ;
truetrueAddEdge(u , v) ;
truetrueAddEdge(v , u) ;
true}
truefor (u = 1 ; u <= n ; u ++ ) {
truetrueif (!done[u]) {
truetruetruert1 = rt2 = 0 ;
truetruetrueGetCycle(u , 0) ;
truetruetrueif (rt1 != 0) {
truetruetruetruememset(vis , false , sizeof vis) ;
truetruetruetruedp(rt1) ;
truetruetruetruetmp = f[rt1][0] ;
truetruetruetruememset(vis , false , sizeof vis) ;
truetruetruetruedp(rt2) ;
truetruetruetrueans += max(tmp , f[rt2][0]) ;
truetruetrue} else {
truetruetruetruememset(vis , false , sizeof vis) ;
truetruetruetruedp(u) ; ans += max(f[u][1] , f[u][0]) ;
truetruetrue}
truetrue}
true}
trueprintf("%lld\n", ans) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章