题解：P10933 创世纪

· · 题解

思路

本题如果将 i 向 a_i 连边，那么就成了基环树内向树森林，不好处理，所以我们将 a_i 向 i 连边，这样就成了基环树外向树森林。

考虑某一棵基环树： 先找到环上的一点 p 断掉 p 与 a_p 的连边，这样就成了一棵以 p 为根的树。 接着设 f_{x,0/1} 表示 x 不选/选时，以 x 为根的子树的最多可以投放的个数。 状态转移方程为 f_{x,0}=\sum\limits_{y \in Son(x)} \max(f_{y,0},f_{y,1})

f_{x,1}=1+\max\limits_{y \in Son(x)}\{f_{y,0}+\sum\limits_{z \in Son(x),z\neq y} \max(f_{z,0},f_{z,1})\}

但其中 f_{x,1} 的转移是可以优化的，进而优化成：

f_{x,1}=1+f_{x,0}-\min\limits_{y \in Son(x)}\{\max(f_{y,0},f_{y,1})-f_{y,0}\}

然后，因为这是忽略了 p 可以限制 a_p 这个条件，所以这是我们可以让 p 强制限制 a_p 这样再计算一次。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int bid,h[N],nxt[N],to[N],n,a[N],f[N][2],ans,km;
bool vis[N];
void add(int x,int y){
    to[++bid]=y;
    nxt[bid]=h[x];
    h[x]=bid;
}
int dp(int x,int d){
    f[x][0]=f[x][1]=0;
    vis[x]=1;
    int res=0,c=1e9+7;
    for(int i=h[x];i;i=nxt[i]){
        int y=to[i];
        if(y==km)continue;
        res=dp(y,d);
        c=min(c,res-f[y][0]);
        f[x][0]+=res;
    }
    f[x][1]=f[x][0]-c+1;
    if(d&&x==a[km])f[x][1]+=c;
    return max(f[x][0],f[x][1]);
}
int hjw(int x){
    for(km=x;!vis[a[km]];vis[km]=1)km=a[km];
    int cnt=dp(km,0);
    dp(km,1);
    return max(cnt,f[km][0]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        add(a[i],i);
    }
    for(int i=1;i<=n;i++)if(!vis[i])ans+=hjw(i);
    cout<<ans;
    return 0;
}