tyvj 创世纪 - 基环树

tyvj 创世纪 - 基环树,第1张

tyvj 创世纪 - 基环树

codevs :   传送门

Description

  上帝手中有着N 种被称作“世界元素”的东西,现在他要把它们中的一部分投放到一个新的空间中去以建造世界。


每种世界元素都可以限制另外一种世界元素,所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的

世界元素能够限制它,这样上帝就可以保持对世界的控制。


由于那个著名的有关于上帝能不能制造一块连自己

都不能举起的大石头的二律背反命题,我们知道上帝不是万能的,而且不但不是万能的,他甚至有事情需要找

你帮忙——上帝希望知道他最多可以投放多少种世界元素,但是他只会O(2N) 级别的算法。


虽然上帝拥有无限多

的时间,但是他也是个急性子。


你需要帮助上帝解决这个问题。


题解

把$A[ i ]$ 当作 $f[ i ]$  即父节点

dfs找环 + 断环 + 重连

只需找到环上的任意两个点记录即可

找到了$x, y$ , 并且$A_x = y$

断环: 让找到的两个点之间的边断开, 从子节点开始$dp$, 算出投放 $x$时的最大值即 $f[x][1]$

重连: 当然不可能真的重连,只需要让 $x$ 不被投放, 并且在处理$y$时, $y$的子节点无需限制它, 因为已经有$x$在限制了

 相当于重连

记得手工栈, 不然会RE

注意一个点组成的环需要一些特判,不然会WA

代码
 #include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define rd read()
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
#define R register
using namespace std; const int N = 1e6 + 1e3; int n, m, fa[N], vis[N];
int f[N][], pos1, pos2, eg;
int tot, head[N]; struct edge {
int to, nxt;
}e[N << ]; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if( c== '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
} int lev;
int st_x[N];
int st_nt[N];
int st_tmp[N]; #define x st_x[lev]
#define nt st_nt[lev]
#define tmp st_tmp[lev] void find_cir(int u) {
st_x[] = u;
lev = ;
start:;
vis[x] = ;
nt = fa[x];
if(vis[nt]) {
pos1 = x; pos2 = nt;
}
else {
st_x[lev + ] = nt;
lev++;
goto start;
}
end:;
if((--lev)) goto end;
} int st_i[N]; #define i st_i[lev] void dp(int u) {
st_x[] = u;
lev = ;
start:;
tmp = ;
f[x][] = f[x][] = ;
vis[x] = ;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == pos1) continue;
st_x[lev + ] = nt;
lev++;
goto start;
end:; f[x][] = f[x][] + max(f[nt][], f[nt][]);
tmp += max(f[nt][], f[nt][]);
}
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == pos1) continue;
f[x][] = max(f[x][], + tmp - max(f[nt][], f[nt][]) + f[nt][]);
}
if(--lev) goto end;
} void dp2(int u) {
st_x[] = u;
lev = ;
start:;
tmp = ;
f[x][] = f[x][] = ;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == pos1) continue;
st_x[lev + ] = nt;
lev++;
goto start;
end:; f[x][] = f[x][] + max(f[nt][], f[nt][]);
if(x == pos2 && pos1 != pos2) f[x][] = f[x][] + max(f[nt][], f[nt][]);
tmp += max(f[nt][], f[nt][]);
}
if(x == pos2 && pos1 != pos2) {
f[x][]++;
if(--lev) goto end;
}
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
f[x][] = max(f[x][], + tmp - max(f[nt][], f[nt][]) + f[nt][]);
}
if(--lev) goto end;
} #undef x
#undef i
#undef nt
#undef tmp int work(int x) {
int maxn = ;
find_cir(x);
dp(pos1);
maxn = f[pos1][];
dp2(pos1);
maxn = max(maxn, f[pos1][]);
return maxn;
} int main()
{
n = rd;
int ans = ;
rep(i, , n) fa[i] = rd, add(fa[i], i);
rep(i, , n) if(!vis[i]) ans += work(i);
printf("%d\n", ans);
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/585577.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表(0条)

保存