题解 P3472 【[POI2008]MAF-Mafia】

· · 题解

题目

题目链接

分析

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

由于顺序不定，所以谁死了对谁有影响都是需要考虑进去的。但是有一点是一定可以肯定的，就是入度为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";
}