[POI2008]枪战Maf
题目
有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。
INPUT
输入n人数<1000000 每个人的aim
OUTPUT
你要求最后死亡数目的最小和最大可能
SAMPLE
INPUT
8
2 3 2 2 6 7 8 5
OUTPUT
3 5
解题报告
考试时候打出了tarjan，然而不会用= =
正解：
tarjan
我们分连通块来考虑
首先自杀的一定死
一个环上的，最多死 点数-1 个（一个人开始开枪，然后被杀，最后只剩一个），最少死一半（假如少于一半，那么必然有至少一条直接相连的边没有被砍，必然还会死人）
一个环加上内向树，最多死 点数-入度为0的个数
最少如何处理呢？
入度为0的死不了（没人打他）
将他们推入队列，他们的目标一定死，那就让他们死，然后他们的目标入度减1，看看是否变为入度为0，依次处理
最后剩下的一定是一堆环
然后就可以在欢声笑语中打出GG
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
int sum();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar());
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum;
}
int n;
struct edge{
int s,e,n;
}a[];
int pre[],tot;
inline void insert(int s,int e){
a[++tot].s=s;
a[tot].e=e;
a[tot].n=pre[s];
pre[s]=tot;
}
inline int my_max(int a,int b){
return a>b?a:b;
}
inline int my_min(int a,int b){
return a<b?a:b;
}
struct node{
int id;
}hh[];
bool die[];
int target[];
int ans_min(),ans_max();
int in[];
int low[],dfn[],zhan[],bl[],size[];
int cnt,top,qlt;
bool vis[];
int cl[];
inline void tarjan(int u){
dfn[u]=low[u]=++cnt;
zhan[++top]=u;
vis[u]=;
for(int i=pre[u];i!=-;i=a[i].n){
int e(a[i].e);
if(!dfn[e]){
tarjan(e);
low[u]=my_min(low[u],low[e]);
}
else
if(vis[e])
low[u]=my_min(low[u],dfn[e]);
}
if(low[u]==dfn[u]){
qlt++;
while(){
int tmp(zhan[top--]);
bl[tmp]=qlt;
vis[tmp]=;
size[qlt]++;
if(tmp==u)
break;
}
}
}
inline bool cmp(node a,node b){
if(cl[bl[a.id]]==cl[bl[b.id]])
return in[a.id]<in[b.id];
return cl[bl[a.id]]<cl[bl[b.id]];
}
queue<int>q;
int now(0x7fffffff),inf(0x7fffffff),fir;
int main(){
memset(pre,-,sizeof(pre));
n=read();
for(int i=;i<=n;i++){
hh[i].id=i;
target[i]=read();
if(target[i]==i){
die[i]=;
bl[i]=++qlt;
cl[qlt]=;
size[qlt]=;
ans_max++,ans_min++;
}
}
for(int i=;i<=n;i++){
if(!die[i]&&!die[target[i]])
insert(i,target[i]),in[target[i]]++;
}
for(int i=;i<=n;i++)
if(!dfn[i]&&!die[i])
tarjan(i);
for(int i=;i<=tot;i++){
int s(a[i].s),e(a[i].e);
s=bl[s],e=bl[e];
if(s!=e)
cl[s]=cl[e]=;
}
for(int i=;i<=qlt;i++){
if(cl[i]==&&size[i]>){
ans_max+=size[i]-;
ans_min+=(size[i]+)>>;
}
}
sort(hh+,hh++n,cmp);
for(int i=;i<=n;i++){
int tmp(hh[i].id);
if(cl[bl[tmp]]==&&!in[tmp]){
now=my_min(now,i);
continue;
}
if(cl[bl[tmp]]==&&in[tmp]){
fir=i;
break;
}
}
if(now!=inf){
ans_max+=n-fir+;
for(int i=now;i<fir;i++)
q.push(hh[i].id);
while(!q.empty()){
int k(q.front());
cl[bl[k]]=;
q.pop();
int tar(target[k]);
if(!die[tar]){
die[tar]=;
cl[bl[tar]]=;
ans_min++;
int kk(target[tar]);
in[kk]--;
if(!die[kk]&&!in[kk])
q.push(kk);
}
}
}
for(int i=;i<=cnt;i++)
if(cl[i])
ans_min+=(size[i]+)>>;
printf("%d %d",ans_min,ans_max);
}