错题重错之枪战Maf

2020 年 7 月 11 日
筆記
图论--拓扑排序

题目描述

有 n 个人，用1∼n 进行编号，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。

Input

输入

人数 n<1000000

接下来 n 个数，依次为每个人的 aim

Output

输出只有一行，共两个数，为要求最后死亡数目的最小和最大可能。

Sample Input

8
2 3 2 2 6 7 8 5

Sample Output

3 5

分析

如果\(a\)瞄准\(b\)，那么我们就从\(a\)到\(b\)建一条有向边

我们设最大存活程度为\(Max\)，最小存活程度为\(Min\)

不难发现，入度为\(0\)的点必定存活（左图中的绿圈）

因为没有人会瞄准他

进一步分析可以发现，建好图后的联通块有两种情况

1、左图（非环）

显然，\(1\)号节点、\(4\)号节点必定存活，而他们所指的\(2\)号节点必死

问题就在\(3\)号节点，如果他先射杀\(2\)号节点，那么他的入度变为\(0\)，存活人数为\(3\)

如果\(2\)号节点先射杀\(3\)，那么三号节点的入度仍为\(1\),存活人数为\(2\)

所以，我们可以向拓扑排序那样维护入度为\(0\)的点，将其放入队列中

队首的目标必死，队首目标的目标可死可不死，打上标记

2、右图（环状）

最小存活：+1（无论如何都会剩一个人）

最大存活：隔一个人打一个，可以最大存活 len/2；

要特别判断自己打自己的环

代码

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
int n,Max,Min,q[maxn],aim[maxn],rd[maxn];
bool die[maxn],undie[maxn];
void Init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&aim[i]);
        rd[aim[i]]++;
    }
    for(int i=1;i<=n;++i)//入度为0的点必活
        if(rd[i]==0){
            Min++;//最小必活数+1
            q[++Max]=i;//队列维护的是入度为0的点
        }
}
void Solve(){
    int head=1;
    while(head<=Max){//扫描队列
        int cur=q[head];head++;//取出队首并出队
        if(die[aim[cur]]) continue;//队首目标已死(多个入度为0的点指向一个点)
        die[aim[cur]]=1;//队首目标必死
        int live=aim[aim[cur]];//队首目标的目标可死可不死，看决策
        rd[live]--;//
        undie[live]=1;//可以让他活，但想死的时候随时可以让他死，在环可以最后死
        if(rd[live]==0)//虽然入度为0，但不一定是必活，所以Min不加
            q[++Max]=live;
    }
    //下面处理只剩下环
    for(int i=1;i<=n;++i)
        if(rd[i] && !die[i]){
            int len=0,flag=0;//len记录环大小,flag标记环上是否有undie的点    
            for(int j=i;!die[j];j=aim[j]){
                len++;
                flag|=undie[j];
                die[j]=1;//标记已死，避免其他的再来计算
            }
            if(!flag && len>1) Min++;//len=1表示自环，必死
            Max+=len/2;
    } 
    printf("%d %d",n-Max,n-Min);
}
int main(){
    Init();
    Solve();
    return 0;
}

Tags: 图论--拓扑排序