bzoj3037--貪心，bzoj3037

bzoj3037--貪心，bzoj3037

題目大意：

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;
}