创世纪

题目描述

applepi手里有一本书《创世纪》,里面记录了这样一个故事……
上帝手中有着N 种被称作“世界元素”的东西,现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素,所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它,这样上帝就可以保持对世界的控制。
由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题,我们知道上帝不是万能的,而且不但不是万能的,他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素,但是他只会O(2^N) 级别的算法。虽然上帝拥有无限多的时间,但是他也是个急性子。你需要帮助上帝解决这个问题。

第一行是一个整数N,表示世界元素的数目。
第二行有 N 个整数$A_1, A_2, …, A_N$。$A_i$ 表示第 i 个世界元素能够限制的世界元素的编号。

$N ≤ 10^6,1≤A_i≤N,A_i≠i$

代码

基环树
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
//想找标程看然后觉得码风奇丑无比
//于是全部都是自己yy的
//意外地AC了

int find(int k){return fa[k] == k? k: find(fa[k]);}//我居然连并查集都不会打了...fa[k] == k直接写成fa[k] != 0
inline void unionn(int x, int y){ fa[find(x)] = find(y); to[x] = y; ++ num[y];}

void help(int k, int ty, int To, int rem, int good){
if(!To){
if(ty) total = good;
else chkmax(total, dp[k][0]);//强制k限制to[k]也就是环的断点
return;
}

chkmin(mint[To], dp[k][1] - dp[k][0]);
dp[To][0] += good, dp[To][1] = dp[To][1] + good + 1 - mint[To];

help(To, ty, to[To], mint[to[To]], max(dp[To][0], dp[To][1]));

dp[To][0] -= good, dp[To][1] = dp[To][1] - good - 1 + mint[To];
mint[To] = rem;//顺序!!!!又查了超级久的错
//回溯
}

int deal(){
r = 0, l = 1;
for(int i = 1; i <= n; ++ i){
mint[i] = MAXN;
if(! num[i]) {
ano[++ r] = i;
mint[i] = 1;
//在下面的while循环中我定义dp[now][1] = dp[now][1] - mint[now] + 1
//所以要定义叶子节点的mint=1让它们不能被选择
}
}

while(l <= r){
int now = ano[l ++];
dp[now][1] = dp[now][1] - mint[now] + 1;//要等出队了才能-mint + 1
int To = to[now], good = max(dp[now][0], dp[now][1]);

if(!(-- num[To])) ano[++ r] = To;

chkmin(mint[To], dp[now][1] - dp[now][0]);
dp[To][1] += good, dp[To][0] += good;
}

for(int i = 1; i <= n; ++ i)
if(num[i] && !vis[(find(i))]) {
vis[find(i)] = 1;
int now = to[i]; to[i] = 0;

if(now == i){
if(mint[now] == MAXN) continue;//整棵树只有根节点
dp[now][1] = dp[now][1] - mint[now] + 1;
ans += max(dp[i][0], dp[i][1]);
continue;
}//自环!!!

if(mint[now] == MAXN) {
//如果now节点只有i一个子节点那么mint值是没有被更新过的
//如果不是我可以自测数据绝对会挂掉
mint[now] = 0;
dp[now][1] = 0;//理解!
}else dp[now][1] = dp[now][1] - mint[now] + 1;

help(now, 1, to[now], mint[to[now]], max(dp[now][0], dp[now][1]));

if(mint[now] || !(mint[now] | dp[now][1])){//i节点的取与否会对dp产生影响
dp[now][1] += mint[now];
if(!dp[now][1]) dp[now][1] = 1;//!!
help(now, 0, to[now], mint[to[now]], max(dp[now][0], dp[now][1]));
}

ans += total;
}
return ans;
}

int main(){
n = read();
for(int i = 1; i <= n; ++ i) fa[i] = i;
for(int i = 1; i <= n; ++ i) unionn(i, read()); //i --> a[i]
printf("%d", deal());
return 0;
}
贪心
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
//代码极短..
//手动模拟还是可以想明白的
//总之是神仙操作
void circle(int now){
int cnt = 0, i = to[now];
to[now] = 0;
for(; i; i = to[i]) ++ cnt, num[i] = 0;
ans += cnt >> 1;
//对于环上的点,我们最多只能取一半那么多(向下取整
}

int main(){
n = read(), l = 1;
for(int i = 1; i <= n; ++ i)
to[i] = read(), ++ num[to[i]];
for(int i = 1; i <= n; ++ i)
if(!num[i]) q[++ r] = i;
while(l <= r){
int now = q[l ++], To = to[now];
if(!num[now] && num[To] > 0){//now和To节点都没有被处理过
num[To] = -1;//标记To节点已经被now节点限制
++ ans;
if(-- num[to[To]] == 0) q[++ r] = to[To];//check爷爷节点是否可以成为新的叶子节点
}
}
for(int i = 1; i <= n; ++ i)
if(num[i] > 0) circle(i);
printf("%d", ans);
return 0;
}