[POI2008]枪战Maf
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 741 Solved: 295
[Submit][Status][Discuss]
Description
有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。
Input
输入n人数<1000000 每个人的aim
Output
你要求最后死亡数目的最小和最大可能
Sample Input
8
2 3 2 2 6 7 8 5
2 3 2 2 6 7 8 5
Sample Output
3 5
HINT
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000100
using namespace std;
int n,cnt;
int a[N];
int du[N];
int head[N];
int vis[N];
int v[N];
int fir[N];
struct node
{
int from,to,next;
}edge[N<<];
int belong[N];
int cnt_du[N];
int siz[N];
int tot;
void init()
{
memset(head,-,sizeof(head));
cnt=;
}
void edgeadd(int from,int to)
{
edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];
head[from]=cnt++;
}
void dfs(int now,int ff)
{
vis[now]=,belong[now]=tot,siz[tot]++;
for(int i=head[now];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(to==now||to==ff||vis[to])continue;
dfs(to,now);
}
}
int check(int now,int num)
{
v[now]=;
int t=now,cntt=;
while(!v[a[t]])
{
v[a[t]]=;
t=a[t];
cntt++;
}
t=a[t];
if(t==now&&cntt==num)return ;
return ;
}
int main()
{
init();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
du[a[i]]++;
edgeadd(i,a[i]);
edgeadd(a[i],i);
}
for(int i=;i<=n;i++)
{
if(!vis[i])
tot++,dfs(i,),fir[tot]=i;
}
for(int i=;i<=n;i++)
{
if(du[i]==)cnt_du[belong[i]]++;
}
int ansma=,ansmi=;
for(int i=;i<=tot;i++)
{
if(siz[i]==)ansma++;
if(check(fir[i],siz[i]))
ansma+=siz[i]-;
else ansma+=siz[i]-cnt_du[i];
}
memset(v,,sizeof(v));
memset(vis,,sizeof(vis));
queue<int>q;
for(int i=;i<=n;i++)
{
if(!du[i])
q.push(i);
}
while(!q.empty())
{
int u=q.front();
q.pop();
v[u]=;
if(!vis[a[u]])
{
v[a[u]]=vis[a[u]]=,ansmi++;
du[a[a[u]]]--;
if(!du[a[a[u]]])
q.push(a[a[u]]);
}
}
for(int i=;i<=n;i++)
{
if(!v[i])
{
int t=i,cnt=;
while(!v[t])
{
v[t]=;
cnt++;
t=a[t];
}
ansmi+=(cnt+)/;
}
}
printf("%d %d\n",ansmi,ansma);
}