首页 > > 程序设计 > C/C++ >

bzoj3037--贪心

2018-06-17 23:29:49来源：未知阅读 ()

题目大意：

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

思路：

其实这题可以转化为最小支配集。但有一种更快的贪心算法。

考虑所有入度为0的点。显然这些点都必须不选。对于每个这些点能控制的点，如果它之前没有被控制，那么选它一定是最优的（自己画个图就知道了）。

所以先更新所有入度为0的点，由于每个点只有一条出边，剩下的点一定能构成几个简单环。而对于每个有n个点的简单环，最多只能选n/2个点。求出所有环就可以计算出答案了。

具体看代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Ans,i,j,k,n,Num,Cnt,m,a[1000001],d[1000001],c[1000001],l=1,r;
bool v[1000001];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),d[a[i]]++;
    for(i=1;i<=n;i++)
    if(!d[i])c[++r]=i;
    while(l<=r)
    {
        if(!v[c[l]]&&!v[a[c[l]]]){
            Ans++;v[a[c[l]]]=1;
            if(--d[a[a[c[l]]]]==0)c[++r]=a[a[c[l]]];
        }
        v[c[l++]]=1;
    }
    for(i=1;i<=n;i++)
    if(!v[i]){
        Cnt=0;
        j=i;
        while(a[j]!=i){
            v[j]=1;
            Cnt++;
            j=a[j];
        }
        v[j]=1;
        Ans+=(Cnt+1)>>1;
    }
    printf("%d",Ans);
    return 0;
}