[bzoj3037/2068]创世纪[Poi2004]SZP_树形dp_并查集_基环树
创世纪 SZP bzoj-3037/2068 Poi-2004
题目大意：给你n个物品，每个物品可以且仅可以控制一个物品。问：选取一些物品，使得对于任意的一个被选取的物品来讲，都存在一个没有被选取的物品，而且选取的个数最大。
注释：$1\le n \le 10^6$。
想法：显然，和骑士类似的，是一个基环树森林。如果A物品可以控制B物品，那就有B物品向A物品连边。对于每一个基环树，如果这个基环树是树的话显然变成树形dp入门题，暴力树形dp即可。然后对于基环树来讲，我们依然记录环上两点，分别以这两点为根，然后特判树形dp即可。
最后，附上丑陋的代码... ...
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 1000010
using namespace std;
int n,m,ans,now,tot;
int to[N],nxt[N],head[N],f[N],g[N],fa[N],ra[N],rb[N];
inline void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int find(int x)
{
return (fa[x]==x)?x:(fa[x]=find(fa[x]));
}
void dfs(int x)
{
int t=1<<30;
g[x]=0;
for(int i=head[x];i;i=nxt[i])
{
if(to[i]!=now)
dfs(to[i]);
g[x]+=max(f[to[i]],g[to[i]]);
t=min(t,max(f[to[i]],g[to[i]])-g[to[i]]);
}
f[x]=g[x]+1-t;
}
int main()
{
scanf("%d",&n);
int a;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
if(find(a)!=find(i))
{
add(a,i);
fa[fa[a]]=fa[i];
}
else
ra[++m]=a,rb[m]=i;
}
for(int i=1;i<=m;i++)
{
dfs(ra[i]),now=ra[i];
dfs(rb[i]),a=f[rb[i]];
f[ra[i]]=g[ra[i]]+1;
dfs(rb[i]),ans+=max(a,g[rb[i]]);
}
printf("%d",ans);
return 0;
}
小结：基环树dp是一种常见的，树形dp带基环树的处理方法。这里有一个问题(By JhinLzh)，问什么输出答案上面的for循环中的第一个dfs有用？明明在第二个dfs中所有的f和g都被更新了，为什么还要dfs？因为在第一个dfs中我们对f是强行负值，这样对于一些叶子节点来讲t值是没有更改的，这就导致f值在最后是一个极小值，这样的f是不会更新答案的。如果不写第一个dfs，使得一些在本不能更新答案的点更新了答案，导致答案错误。所以第一个dfs是必要的。
投递蚂蚁集团等公司10个岗位