[POI2008]MAF-Mafia

缺乏、安全感 2023-10-11 05:31 20阅读 0赞

[题目][Link 1]

大概理解一下这个图是\\(n\\)个点\\(n\\)条边的有向图，也就是一个基环内向树森林

考虑一下一个大小为\\(S\\)的简单环怎么做

画画图就知道，随便找个点顺着打过去，最少可以让\\(\\left \\lceil \\frac\{S\}\{2\}\\right \\rceil\\)个人死；在一个点死之前让它去开一枪，最多可以让\\(S-1\\)个人死

再来考虑一下套在环上的树

首先这些树上有一些入度为\\(0\\)的节点，显然这些节点不可能被打死，于是考虑先这些点

最小化死亡人数，考虑到这些入度为\\(0\\)的点一定要打死人，不如先打死那些被入度为\\(0\\)的点瞄准的人，这样这些人就不能开枪了。所以我们直接按照拓扑序开枪就好了。具体做法就是让一个活着的人去开枪，之后删掉被打死的人的出边，如果产生入度为\\(0\\)的点那么就说明这个点能活下来，就把他加进队列。

这样我们就会搞到环上去，发现一旦我们打死了一个环上的人，那么这个环就会被破坏，按照上面的做法我们就能把这个环处理完。如果一个环的所有点都没有被其子树内的点打死，那么我们就利用上面的结论，环上的死亡人数就是\\(\\left \\lceil \\frac\{S\}\{2\}\\right \\rceil\\)

最大化死亡人数相对好做一下，我们发现对于一棵树来说只有入度为\\(0\\)的点才能活，这样我们就能把状态推到环上去，如果这个环上一旦有一个点被子树里的点射死（其实就是有子树），那么这个环上所有点都能被死。否则死亡人数就是\\(S-1\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=1e6+5;
    int n,tot,q[maxn],ans;
    int atk[maxn],in[maxn],vis[maxn],d[maxn];
    inline void del(int x) {in[atk[x]]--;if(!in[atk[x]]) q[++tot]=atk[x];}
    int find(int x) {
        if(vis[x]) return 0;
        vis[x]=1;
        return find(atk[x])+1; 
    }
    int main() {
        n=read();
        for(re int i=1;i<=n;i++) atk[i]=read(),in[atk[i]]++;
        for(re int i=1;i<=n;i++) if(!in[i]) q[++tot]=i;
        for(re int i=1;i<=tot;i++) {
            int x=q[i];
            if(d[atk[x]]) continue;
            d[atk[x]]=1;
            del(atk[x]);
        }
        for(re int i=1;i<=n;i++) ans+=(d[i]==1);
        for(re int i=1;i<=n;i++) 
        if(in[i]&&!d[i]&&!vis[i]) {
            int now=find(i);
            ans+=(now==1?1:ceil((double)now/2));
        }
        printf("%d ",ans);
        memset(in,0,sizeof(in));memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));ans=0;tot=0;
        for(re int i=1;i<=n;i++) in[atk[i]]++;
        for(re int i=1;i<=n;i++) if(!in[i]) q[++ans]=i;tot=ans;
        for(re int i=1;i<=tot;i++) {
            int x=q[i];
            if(d[atk[x]]) continue;
            d[atk[x]]=1;q[++tot]=atk[x];
        }
        for(re int i=1;i<=n;i++)
        if(!d[i]&&in[i]&&!vis[i]) {
            int now=find(i);
            ans+=(now==1?0:1);
        }
        printf("%d\n",n-ans);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11536100.html

[Link 1]: https://www.luogu.org/problem/P3472