[BZOJ 1124][POI 2008] 枪战 Maf

Description

有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。

Input

输入n人数<1000000 每个人的aim

Output

你要求最后死亡数目的最小和最大可能

Sample Input

8
2 3 2 2 6 7 8 5

Sample Output

3 5

我也不会啊

树DPTH_Hugh
liu_runda

贴代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int a[1000005], Maxn, t, Min, Max;
int times[1000005];
bool die[1000005], nodie[1000005];
int Q[1000005];
int main()
{
    //freopen("maf.in", "r", stdin);
    //freopen("maf.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        times[a[i]]++;
    }
    //Q.resize(1000001);
    for (int i = 1; i <= n; i++)
    {
        if (!times[i])
        {
            Max++;
            Q[++Min] = i;
        }
    }
    //printf("%d\n",Max);

    //for (vector<int>::iterator it = Q.begin(); it != Q.end(); it++)
    for (int i = 1; i <= Min; i++)
    {
        //printf("%d---------%d=======\n",it-Q.begin(),*it);
        int k = a[Q[i]];
        if (die[k])
            continue;
        die[k] = 1;
        nodie[a[k]] = 1;
        --times[a[k]];
        if (!times[a[k]])
        {
            Q[++Min]=a[k]; 
        }
    }
    int sum;
    bool All_NoDied;
    for (int i = 1; i <= n; i++)
    {
        if (times[i] && !die[i])
        {
            sum = 0;
            All_NoDied = 0;
            for (int j = i; !die[j]; j = a[j])
            {
                die[j] = 1;
                sum++;
                All_NoDied |= nodie[j];
            }
            if (!All_NoDied && sum > 1)
                Max++;
            Min += sum / 2;
        }
    }
    printf("%d %d\n", n - Min, n - Max);
}