【BZOJ1124】[POI2008]枪战Maf

Description

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

Input

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

Output

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

Sample Input

8
2 3 2 2 6 7 8 5

Sample Output

3 5

题解：最大：首先入度为0的点一定不会死；另外，如果一个连通块只由一个环组成，那么环中一定有一个人能活下来；但是如果这个环是自环，那么这个人还是得死。

最小：首先入度为0的点一定不会死，那么让他们先开枪，将他们指向的人打死，然后又会出现一些新的入度为0的点，继续做下去即可。最后有一些点没有搜到，那么这些点一定是若干个环，每个环中最少死的人数显然是(siz+1)/2。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

const int maxn=1000010;

int n,m,a1,a2,s1,s2,len,sl;

int to[maxn],f[maxn],siz[maxn],d[maxn];

int r[maxn],vis[maxn];

queue<int> q;

int find(int x)

{

	return (f[x]==x)?x:(f[x]=find(f[x]));

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,u,v,a;

	for(i=1;i<=n;i++)	f[i]=i,siz[i]=1;

	for(i=1;i<=n;i++)

	{

		a=rd(),d[a]++,to[i]=a;

		if(find(a)!=find(i))	siz[f[a]]+=siz[f[i]],f[f[i]]=f[a];

		else	r[++m]=i;

	}

	for(a1=n,i=1;i<=n;i++)	if(!d[i])	q.push(i),a1--;

	for(i=1;i<=m;i++)

	{

		a=find(r[i]);

		for(u=to[r[i]],len=1;u!=r[i];u=to[u],len++);

		if(siz[a]!=1&&len==siz[a])	a1--;

	}

	while(!q.empty())

	{

		u=q.front(),v=to[u],q.pop(),siz[find(u)]--;

		if(!vis[v])

		{

			a2++,vis[v]=1,d[to[v]]--,siz[find(v)]--;

			if(!vis[to[v]]&&!d[to[v]])	q.push(to[v]);

		}

	}

	for(i=1;i<=n;i++)	if(find(i)==i)	a2+=(siz[i]+1)/2;

	printf("%d %d\n",a2,a1);

	return 0;

}