问题描述:

上帝手中有着N 种被称作“世界元素”的东西,现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素,所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它,这样上帝就可以保持对世界的控制。

帝希望知道他最多可以投放多少种世界元素,你需要帮助上帝解决这个问题。

输入:

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

输出:

一个整数,表示最多可以投放的世界元素的数目。

思路:

根据题意,我们可以发现限制关系是一个环加内向树森林,这道题就是一个基环树森林版本的“没有上司的舞会”。因此,这道题的DP转移方程很容易推出,难就难在如何处理基环树森林。

关于基环树上的树形DP我们在BZOJ1791 Island这题中提到过,用的是找出环然后破环为链的方法。然而这道题用这个方法就不好处理,于是我们可以用分类讨论,进行两次DP的方法处理。我们对于每棵基环树找出环上的任意一条边,先假设不用这条边的限制,那么就是一个直接的树形DP,为了方便我们把所有边反着建,把边所在的一个端点作为根节点,然后这样得出了答案一。再假设这条边的限制一定要用到,也是同样的DP只是要一个特判,这样得出的答案二。那么最终的答案就是两个答案中大的那一个。

代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAXN 1000006
using namespace std;

int n, cnt, ans, root, fa[MAXN], head[MAXN], f[MAXN][2];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt; 
}

int find(int x)
{
    if(vis[x]) return x;
    vis[x]=1;
    return find(fa[x]);
}

void dfs(int x, int fa)
{
    f[x][0]=f[x][1]=0; vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==root) continue;
        dfs(to, fa);
        f[x][0]+=max(f[to][0], f[to][1]);
    }
    if(x==fa) {f[x][1]=f[x][0]+1; return;}
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==root) continue;
        f[x][1]=max(f[x][1], f[x][0]-max(f[to][1], f[to][0])+f[to][0]+1);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &fa[i]);
        addedge(fa[i], i);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i])
        {
            root=find(i);
            dfs(root, 0);
            int temp=max(f[root][0], f[root][1]);
            dfs(root, fa[root]);
            temp=max(f[root][0], temp);
            ans+=temp;
        }
    printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注