BZOJ1040 [ZJOI2008]骑士

题意

​ 给你一个由许多个(树加上一条边(可能叫环套树))组成的类似森林的东西。然后你可以选择一些点,要求这些点两两之间没有连边N<=1000000N <= 1000000

题解

​ 我们考虑如果是树怎么做?

​ 显然这是一个无向的,先随便找一个root,然后我们可以用树形DP,每一棵树单独处理

​ 用f[i]f[i]表示第i个点选,g[i]g[i]表示第i个点不选,这样能得到的最大价值。

​ 大家应该都会吧。

​ 那么有环呢?

​ 我们可以一遍DFS找出环,记录环上多出来的一条边。

​ 我们强制断开这条边,对于这条边两端的两个点强行跑一遍DP,得到两个g[i]g[i]中大的一个,这就是这个图的答案。

​ 为什么?显然两个点不能同时选,所以一个点不选,另一个点就有几率选。

​ 具体证明我不会,大家自行yyyy

附上代码

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
//Hello Wolrd
//There is Special Pig Jiong in the world.
#pragma GCC optimize("O3")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define gc getchar
#define pc putchar
inline int read(){int x=0,f=1;char c=gc();for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(;c>='0'&&c<='9';c=gc())x=x*10+c-48;return x*f;}
inline void write(int x){if(x < 0) putchar('-'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
inline void writeln(int x){write(x);puts("");}
const int oo = 0x3f3f3f3f;const int inf = oo;
#define mem(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
#define mp make_pair
typedef unsigned long long ull;
typedef long long ll;
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define file(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define N 1000005
struct Edge{
int to,nxt;
Edge(){}
Edge(int to,int nxt):to(to),nxt(nxt){}
}edge[N*2];
int first[N],nume;
void Addedge(int a,int b){
edge[nume] = Edge(b,first[a]);
first[a] = nume++;
}
pii x;
int tmp;//保存应该断的边
bool vis[N];
void find(int u,int fa){
vis[u]=true;
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(v == fa) continue;
if(vis[v]){
x.first=u,x.second=v;
tmp = e/2;
continue;
}
find(v,u);
}
}
ll f[N],g[N],res,ans;
int a[N];
int flag;
void DP(int u,int fa){
f[u] = a[u],g[u] = 0;
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(v==fa)continue;
if(tmp==e/2) continue;
DP(v,u);
f[u]+=g[v];
g[u]+=max(f[v],g[v]);
}
}
int n;
int main(){
n = read();
mem(first,-1);nume = 0;
rep(i,0,n){
int x;
a[i] = read(),x = read()-1;
Addedge(x,i);
Addedge(i,x);
}
mem(vis,false);
ans = 0;
rep(i,0,n){
if(vis[i]) continue;
find(i,-1);
flag = 0;DP(x.first,-1);
res = g[x.first];
flag = 1;DP(x.second,-1);
res = max(res,g[x.second]);
ans += res;
}
printf("%lld\n",ans);
return 0;
}
/*
4
10 2
5 1
10 4
5 3
*/
文章目录
  1. 1. 题意
  2. 2. 题解