自动搬运

查看原文

来自洛谷，原作者为

	Vocanda 这个蒟蒻很菜，什么也没有留下

搬运于2025-08-24 21:49:21，当前版本为作者最后更新于2020-07-11 20:31:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

题目链接

分析

正如标签，贪心！没错，这个题的思想就是贪心了。

由于顺序不定，所以谁死了对谁有影响都是需要考虑进去的。但是有一点是一定可以肯定的，就是入度为$0$的点，也就是没有被人用枪指着的人的目标是必死的，因为没有人会杀死他而让他的目标存活。由于我们要求的就是死的最多和最小，那么我们逆向思考一下，我们就可以求出最大存活和最小存活数，最后减一下就好了。

我们利用一个队列来存储一定活着的人，也就是入度为$0$的人，每一次取出队首，然后将当前这个人的目标标记为死人……然后显然，这个死了的人的目标的入度就减一了。如果当前入度变成了$0$，那么这个人就可以放到队列里，让后让或者的最大人数加一，并且标记为没死。至于为什么不把最小存活也加一呢，因为这个人不一定会活着，只有目标为他的点死了，他才能够活，所以只把最大的存活人数加一。

处理完这样的单点之后，我们就应该处理环了，分析一下，我们可以得出，如果让环里的人死的最多，那么可以通过一定的顺序，让最后只剩下一个人，而死的最少的情况就是死一半。我们在扫描环的时候，记录一下是否有没有死的，并且记录环的大小，最后如果环里有能不死的，且环的长度大于一，那么一定有一个人没死，所以就让$Min++$，不然就不管。最后再让最大值加上环大小的两倍，最后只需要用总人数减去$Max$和$Min$就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int q[maxn];
int Max,Min;
int die[maxn],undie[maxn];
int to[maxn];
int n;
int rd[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>to[i];
		rd[to[i]]++;//记录入度
	}
	for(int i=1;i<=n;++i){
		if(rd[i] == 0){//入度为0就死不掉
			Min++;//最小人数++
			q[++Max] = i;//最大人数++并且入队
		}
	}
	int head = 1;
	while(head<=Max){
		int cur = q[head];//取出队首
		head++;
		if(die[to[cur]])continue;//如果死了就continue
		die[to[cur]] = 1;//没死的话他的目标一定死，标记
		int li = to[to[cur]];
		rd[li]--;//他的目标的目标入度减一
		undie[li] = 1;//标记可以不死
		if(!rd[li]){//入度为0就入队，但是Min不加
			q[++Max] = li;
		}
	}
	for(int i=1;i<=n;++i){//下边就剩下环了
		int len = 0,flag = 0;
		if(rd[i] && !die[i]){//有入度，没死，就从这里开始
			for(int j=i;!die[j];j=to[j]){//一个个找环里的人
				len++;//环长度++
				flag|=undie[j];//看是否有不死的
				die[j] = 1;//标记死亡
			}
		if(!flag && len>1)Min++;//有可以不死的并且长度大于1,因为等于一就是自环，必死
		Max += len/2;//活的最大人数加上环长度的二分之一
		}
	}
	cout<<n-Max<<" "<<n-Min<<"\n";
}