UOJ Logo Capella的博客

博客

非本 OJ 题目可以吗qwq 《杀人游戏》Tarjan

2018-06-09 18:26:16 By Capella

写在前面

手动 @AZe

这是个 Tarjan 好题 qwq

那啥先给自己打个广告qwq


[BZOJ 2438] 中山市选2011 杀人游戏

<题目链接>


AZe 问的题目,上手发现确实好题 qwq。

如何求出题目要求的概率?

根据题目描述,我们知道,警察调查未知身份者就有可能会死亡,所以查的人越少越安全。

因此,安全查出必须调查的未知身份者数总人数 $P_{安全查出} = 1 -\frac{必须调查的未知身份者数}{总人数}$。

如果有一群人,他们直接或间接认识,那么他们可以看作一个点。

于是想到 Tarjan 求 SCC,缩点建新图(原因过后交代)。

查一个点,这个点认识的点,都可以明确身份。

所以,查所有新图上入度为 $0$ 的点即可,数出个数 $\mathrm{ans}$。

特殊情况如下:如果有一个人 $x$ 被孤立,即,$x$ 所在的 SCC $\mathrm{size}$ 为 $1$,且 $x$ 认识的每个人都不仅仅被 $x$ 认识(判断这步需要在新图上遍历 $x$ 所在点的邻接点,所以需要建新图),这时候不需要询问 $x$ 便可以确定其身份。这时候需 --$\mathrm{ans}$。

答案即 $1 - \frac{ans}{n}$。

#include <algorithm>
#include <cstdio>
#include <set>
#include <stack>
const int MAXN=100010;
int n,m;
class Graph
{
    private:
        int V;
    public:
        Graph(int n)
        {
            V=n;
            for(int i=1;i<=V;++i)
                head[i]=nullptr;
        }
        ~Graph(void)
        {
            for(int i=1;i<=V;++i)
                delete head[i];
        }
        struct Edge
        {
            int to;
            Edge *next;
            Edge(int to,Edge* next):to(to),next(next){}
            ~Edge(void)
            {
                if(next!=nullptr)
                    delete next;
            }
        }*head[MAXN];
        void AddEdge(int u,int v)
        {
            head[u]=new Edge(v,head[u]);
        }
}*G1,*G2;
namespace Tarjan
{
    bool exist[MAXN];
    int cnt,sum,ans,DFN[MAXN],low[MAXN],SCC[MAXN],size[MAXN],in[MAXN];
    std::set<std::pair<int,int> > S;
    std::stack<int> st;
    void DFS(int u)
    {
        st.push(u);
        exist[u]=true;
        DFN[u]=low[u]=++cnt;
        for(Graph::Edge *i=G1->head[u];i!=nullptr;i=i->next)
        {
            int v=i->to;
            if(!DFN[v])
            {
                DFS(v);
                low[u]=std::min(low[u],low[v]);
            }
            else if(exist[v])
                low[u]=std::min(low[u],DFN[v]);
        }
        if(DFN[u]==low[u])
        {
            ++sum;
            for(int v=0;u^v;)
            {
                exist[v=st.top()]=false;
                st.pop();
                ++size[SCC[v]=sum];
            }
        }
    }
    void Contract(void)
    {
        for(int u=1;u<=n;++u)
            for(Graph::Edge *i=G1->head[u];i!=nullptr;i=i->next)
            {
                int v=i->to;
                if(SCC[u]^SCC[v] && !S.count(std::make_pair(SCC[u],SCC[v])))
                {
                    ++in[SCC[v]];
                    G2->AddEdge(SCC[u],SCC[v]);
                    S.insert(std::make_pair(SCC[u],SCC[v]));
                }
            }
    }
    bool Judge(int u)
    {
        if(in[u] || size[u]!=1)
            return false;
        for(Graph::Edge *i=G2->head[u];i!=nullptr;i=i->next)
            if(in[i->to]==1)
                return false;
        return true;
    }
    void Run(void)
    {
        for(int i=1;i<=n;++i)
            if(!DFN[i])
                DFS(i);
        G2=new Graph(sum);
        Contract();
        for(int i=1;i<=sum;++i)
            if(!in[i])
                ++ans;
        for(int i=1;i<=sum;++i)
            if(Judge(i))
            {
                --ans;
                break;
            }
        printf("%.6lf\n",(double)(n-ans)/n);
    }
}
int main(int argc,char** argv)
{
    scanf("%d %d",&n,&m);
    G1=new Graph(n);
    for(int i=1,x,y;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        G1->AddEdge(x,y);
    }
    Tarjan::Run();
    return 0;
}

谢谢阅读。

评论

Capella
@AZe 原文圈人失败
poorpool
这个其实是我校这几天的考试题>_<
lris
nullptr怎么才能使用呢qwq
NaCl
貌似 NOIp 禁止自定义曌(命名空间)?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。