【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;
}
05-11 22:13