錯題重錯之槍戰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: 圖論--拓撲排序