2017.07.10【NOIP提高组】模拟赛B组 创世纪 题解

原题：

http://172.16.0.132/senior/#contest/show/2045/2

题目描述：

上帝手中有着n种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。
由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2^n)级别的算法。虽然上帝拥有无限多的时间，但是他也是个急性子。你需要帮助上帝解决这个问题。

输入：

第一行一个正整数n，表示世界元素的数目。
第二行n个正整数a_1, a_2, ..., a_n。a_i表示第i个世界元素能够限制的世界元素的编号。

输出：

最多可以投放的世界元素的数目。

样例输入：

6
2 3 1 3 6 5

样例输出：

3

样例说明：

选择2、3、5 三个世界元素即可，分别有1、4、6来限制它们。

数据范围限制：

30%的数据，n<=10。
60%的数据，n<=10^5。
100%的数据，a_i<=n<=10^6。

分析：

贪心。
找出所有没有入度的点，那么这些点必定不能选入集合中，我们沿着这些点上溯，将可以选进集合的点都选进集合。
这里“可以选进”的定义为存在一个没有被选进集合的前驱。
于是环上就会有若干个由树上决定它要选进集合的点。
我们将环按照已选入集合的点来分裂成若干段，每一段按照原来的贪心方法来贪心即可。

贪心正确性的证明：

我们将一个点从“选”的状态变成不选，显然不会改变其前驱的状态（前驱并不依赖于这个点），那么我们考虑一下后继的情况。
如果这个点x的唯一的后继y并没有被选入，那么说明它原来所有的前驱都被选入了。我们可以将它选入点集中。但是这样子可能导致y的唯一后继z无法被选入了（这种情况就是z被选入点集时依赖于y），从下图可以更直观地看出这种关系。

图片1.png

那么这时候我们就可以有两种选择，直接舍弃绿叉边，又或者将它继续往下“推”，那么递归地来看这和我们做的第一步是相同的，显然这么做并不能使得被选入边集的边数增多。
如果这个点x的唯一的后继y被选入了，那么情况是类似的，不难证明不会使得边数增多。
综上所述，通过上面所述的贪心策略能选出最大的点集。

实现：

#include<cstdio>

const int maxn=1000010;  
int a[maxn],team[maxn],head,tail,n;  
int rd[maxn];  
int ans;  
bool bz[maxn];  
  
int main()  
{  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
        scanf("%d",&a[i]),rd[a[i]]++;  
    for(int i=1;i<=n;i++)  
        if(!rd[i])  
            team[++tail]=i;  
    while(head<tail)  
    {  
        int t=team[++head];  
        if(!bz[t]&&!bz[a[t]])  
        {  
            bz[a[t]]=1;  
            ans++;  
            if(!--rd[a[a[t]]])  
            {  
                team[++tail]=a[a[t]];  
            }  
        }  
        bz[t]=1;  
    }  
    for(int i=1;i<=n;i++)  
    {  
        if(!bz[i])  
        {  
            int t=1;  
            bz[i]=1;  
            int c=i;  
            while(a[c]!=i)  
            {  
                c=a[c];  
                bz[c]=1;  
                t++;  
            }  
            ans+=t>>1;  
        }  
    }  
    printf("%d",ans);
}