题解：P3472 [POI 2008] MAF-Mafia

· · 题解

Solution

考虑建图，从 i\to s_i 连边，这就是一个基环森林。
题目等价于保留若干个节点，使得这些节点均不相邻，即独立集问题。
这是因为，若两个点是相邻的，则其中的父亲 u 就必然存活，于是他就必然会开枪，那么 s_u，就是与之相邻的那个节点就必然会死去，这就与之矛盾了。

首先，死去的人最多是好做的，只需要保留必要的节点（入度为 0），或者单环即可。

把环视为树根，首先预处理出树根的每个子树的独立集的贡献，自下往上，记 \mathrm{dp}_u(0/1) 表示 u 的子树内，u 号节点选或者不选，子树能选的做多的节点个数。记到环上的每一个点，于是问题就变成了环上的带权最大独立集，多一维记录初始选取的节点是否保留即可。

可能有些节点的一些状态是不能到达的，设成 -1，转移的时候特判即可。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e6+10,mod=998244353;
typedef pair<int,int> pii;
typedef long long ll;
/*

*/
int C,T=1;
int s[N],n,deg[N],dp[N][2];
int f[N][2][2],fu[N],cnt[N];
int fnd(int u) {return u==fu[u]?u:fu[u]=fnd(fu[u]);}
void merge(int u,int v){u=fnd(u),v=fnd(v);if(u!=v) fu[u]=v;}
void Lain(){
    cin>>n;
    for(int i=1;i<=n;i++) fu[i]=i;
    for(int i=1;i<=n;i++)
        cin>>s[i],deg[s[i]]++,merge(i,s[i]);

    queue<int> q;
    for(int i=1;i<=n;i++) if(!deg[i])
        q.push(i),dp[i][0]=-1,++cnt[fnd(i)];
    while(!q.empty()){
        int u=q.front(),v=s[u]; q.pop();
        if(~dp[u][1]) ++dp[u][1]; 
        if((~dp[u][1]||~dp[u][0])&&~dp[v][0]) dp[v][0]+=max(dp[u][1],dp[u][0]);
        if(dp[u][0]==-1) dp[v][1]=-1;
        else if(~dp[v][1]) dp[v][1]+=dp[u][0];
        --deg[v]; if(!deg[v]) q.push(v);
    }
    ll res=0,rm=0;
    for(int i=1;i<=n;i++) if(fnd(i)==i){
        rm+=cnt[i];
        if(!cnt[i]&&s[i]!=i) rm++;
    }
    for(int i=1;i<=n;i++) if(s[i]==i)
        deg[i]=0,res+=dp[i][0];
    for(int i=1;i<=n;i++) if(deg[i]){ deg[i]=0;
        f[i][0][1]=f[i][1][0]=-1; int u=s[i];
        f[i][0][0]=dp[i][0],f[i][1][1]=dp[i][1];
        while(u!=i){ deg[u]=0;
            for(int p:{0,1})
                f[u][1][p]=dp[u][1],
                f[u][0][p]=dp[u][0];
            u=s[u];
        }
        while(s[u]!=i){
            int v=s[u];
            for(int p:{0,1}){
                if(~f[u][1][p]) ++f[u][1][p];
                if((~f[u][1][p]||~f[u][0][p])&&~f[v][0][p]) f[v][0][p]+=max(f[u][1][p],f[u][0][p]);
                if(f[u][0][p]==-1) f[v][1][p]=-1;
                else if(~f[v][1][p]) f[v][1][p]+=f[u][0][p];
            }

            u=v;
        }
        if(~f[u][1][0]) f[u][1][0]++;
        int tmp=max({f[u][1][0],f[u][0][1],f[u][0][0]});
        if(~tmp) res+=tmp;
    }
    cout<<n-res<<" "<<n-rm;
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
//  cin>>C>>T;
    while(T--) Lain();
    return 0;
}