P4819 杀人游戏：缩点、重边判断与概率

· · 题解

题目描述

有向图中有若干白点和一个黑点，每个点为黑点概率相等。每次可以任选一个点发起询问，询问结果为该点能直接到达的所有点的颜色。

求最优情况下不对黑点发起询问且得知黑点标号的概率。

解法

首先考虑连通性。容易发现的一条性质：如果对某个强连通分量中的任意一点发起询问，只要该点不是黑点，我们就能在没有任何风险的情况下得知该强连通分量中所有点的颜色。

因此可以确定解决本题的第一个步骤：缩点，将所有强连通分量看作一个点。此时图转化为一张 DAG。

继续思考。在得到的 DAG 中，如果某个点有入边，那么与其先询问该点，不如先对向该点有出边连接的点发起询问。原因很简单：如先对该点发起询问，那么我们无法得知向该点有出边连接的点的颜色，之后一定需要向上发起另一次询问，这样会有更大的风险。同时，如果当前点是黑点，先询问该点会直接失败，而如果先询问向该点有出边连接的点，我们就会在询问黑点前就得知黑点的标号。综上所述，询问向该点有出边连接的点显然更划算。

因此可以得出一个结论：在新图中，我们只需要对入度为 0 的点发起可能遇到黑点的询问。如果在这些询问中没有遇到黑点，之后的询问就绝对安全了。

我们可以依据这个结论对答案进行猜测：设缩点后新图中入度为 0 的点数量为 c，则答案应为 1-\frac{c}{n}。

这个答案已经很接近正解了，但并不完全正确，仍然有特殊情况存在。

考虑原图中一个单独的点 p。若 p 的入度为 0，且 p 可直接到达的所有点入度均\geq2（或者 p 没有出边），此时如果我们把 p 置于询问队列的最后，那么在对 p 发起询问之前，与 p 相连的所有点的颜色都已经确定了。如果黑点在这些点当中，我们自然没有必要再对 p 进行询问了。如果最后我们仍没有确定黑点标号，那么 p 是黑点，同样无需对 p 发起询问。

因此，如果图中存在至少一个入度为 0 且 size=1 的强连通分量，答案就会变为 1-\frac{c-1}{n}，注意答案只能变化一次。

解题思路到这里就整理完毕了，但代码实现上还有一点小问题：在原图中，一个点可能有多条连接某一其他强连通分量的出边。这样一来缩点过后会出现重边，有可能会导致统计答案的过程中误判一些点的入度而出现错误。

由于之前数据没有特意卡这个点，许多没有对这一问题进行处理的代码也可以通过。现在数据已加强，缩点不去重边的代码无法 AC。现有的另一篇题解使用 map 进行记录以达到防止重复加边的目的，这里提供另一种方法：在新图中加入某个点的出边时，给已经连接过的其他点打上标记，加完该点的所有出边后清除标记。

至此，本题得到完美解决。

代码

#include<cstdio>
#include<map>
int dfn[300086],low[300086],h[300086],hh[300086],inv[300086],col[300086],st[300086],sze[300086];
int n,m,tot,cnt,top,u,v,C,dfncnt;
bool vis[300086],vv[300086];
struct asdf{
    int v,nxt;
}e[600086],ee[600086];
struct asd{
    int u,v;
}E[300086];
int read(){//简单快读
    char ch=getchar();int nn=0,ssss=1;
    while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
    return nn*ssss;
}
bool add(int u,int v){
    e[++tot].v=v;
    e[tot].nxt=h[u];
    h[u]=tot;
    return true;
}
bool addedge(int u,int v){
    ee[++tot].v=v;
    ee[tot].nxt=hh[u];
    hh[u]=tot;
    inv[v]++;
    return true;
}
bool tarjan(int np){//缩点
    dfn[np]=low[np]=++dfncnt;
    st[++top]=np;vis[np]=true;
    for(int i=h[np];i;i=e[i].nxt){
        if(!dfn[e[i].v]){
            tarjan(e[i].v);
            if(low[e[i].v]<low[np])low[np]=low[e[i].v];
        }
        else
            if(vis[e[i].v]&&dfn[e[i].v]<low[np])low[np]=dfn[e[i].v];
    }
    if(low[np]==dfn[np]){
        C++;
        while(st[top+1]!=np){
            vis[st[top]]=false;
            col[st[top]]=C;
            sze[C]++;
            top--;
        }
    }
    return true;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        scanf("%d%d",&E[i].u,&E[i].v);
        add(E[i].u,E[i].v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
    tot=1;
    for(int i=1;i<=n;i++){
        for(int j=h[i];j;j=e[j].nxt){
            if(col[i]==col[e[j].v]||vv[col[e[j].v]])continue;
            addedge(col[i],col[e[j].v]);
            vv[col[e[j].v]]=true;//打标记防止重复加边
        }
        for(int j=h[i];j;j=e[j].nxt)vv[col[e[j].v]]=false;//删除标记
    }
    bool flag=true;
    for(int i=1;i<=C;i++){
        if(!inv[i])cnt++;//统计无入边的点 
        if(inv[i]||sze[i]>1)continue;
        if(flag){
            bool pp=true;
            for(int j=hh[i];j;j=ee[j].nxt)
                if(inv[ee[j].v]<=1){
                    pp=false;
                    break;
                }
            if(pp)cnt--,flag=false;//如果某个强连通分量size为1且指向的点入度均>1,则该点可以不访问 
        }
    }
    printf("%.6lf",(double)(n-cnt)/n);
}

碎碎念

欢迎指出错误，蚂蜂略丑求原谅

upd:发现一处笔误，进行了修改