1124: [POI2008]枪战Maf
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 335 Solved: 130
[Submit][Status]
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
看网上的代码，理出来的思路，代码和网上的不一样，我用的栈来维护
虽然AC了，但还是有些不明白的地方
得到的图一定是一条条链指向一个环或者没有环
最多就让入度为0的都活着，一遍dfs，记录vis
剩下的没有vis的一定是环
剩下的每个环只剩一个
有可能原本有环，全都死亡
环一定是独立的环
最少：
首先考虑入度为0的点
他指向的一定先死，反正早晚都要死，晚死不如早死，
晚死他还多打死几个（这个不严密，感觉有漏洞），
他死了之后更新入度，重复这个过程
剩下的也是环的处理
偶数环打死一半
奇数环打死一半（上取整）
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
const int N=1000010;
int n;
int point[N];
int ind[N];
bool vis[N];
int ans1;
int t;
stack<int>s;
/////////////////////////////////////////////////
void dfs1(int u)
{
vis[u]=1;
t++;
if(!vis[point[u]]) dfs1(point[u]);
}
void dfs2(int u,bool kill)
{
vis[u]=1;
if(kill) ans1++;
if(kill && --ind[point[u]]==0) s.push(point[u]);
if(!kill && !vis[point[u]]) dfs2(point[u],!kill);
}
/////////////////////////////////////////////////
void input()
{
scanf("%d",&n);
rep(i,1,n) scanf("%d",&point[i]),ind[point[i]]++;
}
void solve()
{
///////////////////init///////////////////
int ans2=0;
////////////////calculate////////////////
rep(i,1,n) if(ind[i]==0)
{
dfs1(i);
ans2++;
}
rep(i,1,n) if(point[i]!=i && !vis[i])
{
dfs1(i);
ans2++;
}
ans2=n-ans2;
MS(vis,0);
rep(i,1,n)
{
if(ind[i]==0) s.push(i);
}
while(!s.empty())
{
int u=s.top(); s.pop();
dfs2(u,0);
}
rep(i,1,n)
{
if(!vis[i])
{
t=0;
dfs1(i);
ans1+=(t+1)/2;
}
}
/////////////////output/////////////////
printf("%d %d\n",ans1,ans2);
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("std.out","w",stdout);
#endif
input();
solve();
#ifdef _TEST
for(;;);
#endif
return 0;
}