题解：P10933 创世纪

· · 题解

题意

可以抽象成一个图论问题。

给你 n 个点的有向图，每个点恰好有一个出边（可能有自环），选出尽可能多的点，使得每个被选出的点 x，都至少有一个指向 x 的点没被选。

思路

可以想到 DP。

这是一棵树吗？显然不是，因为边数等于点数，那就是一棵基环树了！！！

基环树 DP 的一般思路就是先断掉一条边，使其变成一个普通的树形 DP 进行求解，最后考虑上删边的影响。

那我们就先考虑这个树上的 DP。

树上 DP

和没有上司的舞会很像。

状态

设 dp_{u,0/1} 表示以 u 为根的子树，并且选或不选 u 最多能选择的点数。

算是一个经典模型了，一般都会这么设。

转移方程

如果 u = 0，那么他的儿子都可以选，当然也可以不选。所以求最大值。转移方程就是 dp_{u,0}=\sum{\max(dp_{v,0},dp_{v,1})}。

如果 u = 1，那么他至少要有一个儿子不选，不选的儿子肯定是值最小的，这样 dp_{u,1} 才会大。即 dp_{u,1} = 1 + dp_{u}{0} - \min(dp_{v,1} - dp_{v,0})。

边界条件

因为要求和，所以全赋值为 0，即 dp_{u,0/1} = 0。

删边

用两次 DP 来解决。

考虑 u 选不选，一次设 u 要选，一次设 u 不选。

最后答案取最大值就行了。

代码

细节都在注释里。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;

int n,a[N];

vector<int> e[N];

int dfn[N],dp[N][2];

int vis[N];
void dfs(int u,int root,bool flag){
    dfn[u] = true;
    int mi = INF;
    for (auto v :e[u]){
        if (v == root) continue;//防止死循环
        dfs(v,root,flag);
        dp[u][0] += max(dp[v][1],dp[v][0]);
        mi = min(dp[v][1] - dp[v][0],mi);//维护最小值
    }
    dp[u][1] = 1 + dp[u][0];
    if (u != a[root] or !flag){ 
        if (mi >= 0) dp[u][1] -= mi;
    }
}
int main()
{
    int n;cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
        e[a[i]].push_back(i);//还要在树的内部 DP，所以建反图
    }
    int sum = 0;
    for (int x = 1;x <= n;x++){//基环森林
        if (!dfn[x]){
            while(!vis[x]){
                vis[x] = true;
                x = a[x];
            }//求环
            dfs(x,x,1);
            int ans = dp[x][0];
            dfs(x,x,0);
            sum += max(dp[x][1],ans);
        }

    }
    cout << sum;
    return 0;   
}