题解 P4819 【[中山市选]杀人游戏】

IronELement · 2018-10-18 15:11:30 · 题解

这题看起来是很恶心的概率题。
不过想清楚其实也没有那么难。
下面根据一些样例图来讲几种情况。

这是样例的图。根据题目，每个人是杀手的概率是相同的。在这里是1/5，即0.2。容易发现，如果调查第一个人（最优情况），而且这个人不是杀手，就能知道所有人的信息。而第一个人是杀手的概率为0.2,成功的概率就是1-0.2=0.8。

同样的，这里也是从1开始调查。如果1是平民，那么1,2,3,4的情况就全部清楚了。因为1是平民时，可以获知2的情况，如果2是杀手，那么不需要再调查了。如果2是平民，2会提供3的信息,以此类推。

换句话说，从甲开始调查所能了解到情况的人，就是从图上甲对应的点出发，可以遍历到的所有点
转化
从第二张图我们可以发现，点集(2,3,4)中，只要了解了其中一个点，其他点的情况也清楚了。这就是一个强联通分量。我们可以用Tarjan算法把这样的所有点集缩成一个点，方便后面的处理。关于Tarjan算法，这里就不仔细解说了。可以参照一下蒟蒻写的另外一篇博客。
缩点后，上面的第二张图就转化成这样。

这样问题就转化为了求有多少个入度为0的点（缩点后必定有入度为0的点，而从这些点出发，必定最优）。有多少个点，就要调查多少次。生命受到威胁的概率就是

(1/n)*num

但是
再看转化后的第二张图。调查1后，1和（2,3,4）的情况都明白了。这时候，杀手如果在1,2,3,4中，不用继续调查了。如果不在1,2,3,4中，那么5必定是杀手，也不用继续调查！这个样例的答案是0.8。

可以不调查最后一个点的情况 这里先说明，如果一个点，在缩点前也是一个点，指向的点的入度都大于1，且入度为0，那么这个点在最后可以不调查。下面给出证明： 1.入度为0。只有这样才能最优。

例如在这个图中，如果从入度不为0的2开始调查，那么指向2的1必定不能调查到。因此不是最优的。

2.指向的点入度大于1。
在第二张图缩点后的图的基础上，如果增加一个6指向5。这时1和6都是入度为0。但此时从1开始后，只能弄清楚1和（2,3,4）的情况，5的情况是不清楚的，这时候如果不调查6，不能确定的点有两个。

3.缩点前仍然是一个点 缩点后，这个图看起来可以从5调查起，然后5和4的情况都清楚了，剩下一个（1,2,3）。但是，再看看缩点前的图。

其实还剩下3个点，还需要从其中一个再调查一次。
4.此外补充一点，如果一个点是出度为0，入度也为0，那么这个点如果放在最后，也可也不调查。

注意 这里重构图的时候，一定要去重边，否则会对出度和入度的判断造成影响。
这里感谢一下某大佬教蒟蒻用map去重边。

丑代码和注释

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <ctime>

using namespace std;

int n,m,i,j,k,l,dfn[100010],low[100010],scc[100010],ti,sc,pnum[100010],ind[100010],need,outd[100010];
bool p;
double per;

vector<int>to[100010];
vector<int>newto[100010];
stack<int>s;
map<int,int>edge[100010];

void Tarjan(int now)
{
    int i,j;
    dfn[now]=++ti;
    low[now]=dfn[now];
    s.push(now);
    for(i=0;i<to[now].size();i++)
    {
        int next=to[now][i];
        if(dfn[next]==-1)
        {
            Tarjan(next);
            low[now]=min(low[now],low[next]);
        }
        else
        if(scc[next]==-1)
        {
            low[now]=min(low[now],dfn[next]);
        }
    }
    if(dfn[now]==low[now])
    {
        int snow;
        sc++;
        while(true)
        {
            snow=s.top();
            s.pop();
            scc[snow]=sc;
            if(snow==now)break;
        }
    }
}

void Reconstruction()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<to[i].size();j++)
        if(scc[i]!=scc[to[i][j]]&&!edge[scc[i]][scc[to[i][j]]])//判自环和map判重边
        {
            newto[scc[i]].push_back(scc[to[i][j]]);
            edge[scc[i]][scc[to[i][j]]]=1;
            ind[scc[to[i][j]]]++;
            outd[scc[i]]++;
        }
        pnum[scc[i]]++;
    }
}

int main()
{
    freopen("kill.in","r",stdin);
    freopen("kill.out","w",stdout); 
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        to[u].push_back(v);
    }
    for(i=1;i<=n;i++){dfn[i]=-1;scc[i]=-1;}
    for(i=1;i<=n;i++)
    {
        if(dfn[i]==-1)
        {
            Tarjan(i);
        }
    }
    Reconstruction();//重构图
    p=0;
    for(i=1;i<=sc;i++)
    {
        if(ind[i]==0)
        {
            need++;//需要调查的人加一
            if(pnum[i]==1)//如果缩点前是1个点
            {
                if(outd[i]==0)p=1;//入度为0出度为0，特判
                else
                {
                    bool p2=1;
                    for(j=0;j<newto[i].size();j++)
                    {
                        int next=newto[i][j];
                        if(ind[newto[i][j]]<=1)
                        {
                            p2=0;
                            break;
                        }
                    }
                    //检查是否所有指向的点的入度都大于1
                    if(p2)p=1;
                }
            }
        }
    }
    if(p)need--;//最后一个不查
    per=1.0/(n*1.0);;
    printf("%.6lf",1-per*need);
    return 0;
}

蒟蒻写文，如有不当，请不留情面地打脸！