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

题目描述

一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，

查出谁是杀手。

警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。

现在警察掌握了每一个人认识谁。

每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。

问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

输入输出格式

输入格式

第一行有两个整数 N,M。

接下来有 M 行，每行两个整数 x，y，表示 x 可以续y（y 不一定可以续 x,例如贠启豪同志）。

输出格式

仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。

输入输出样例

输入样例1

输出样例1

0.800000

说明

警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概率是0.8。

对于 100%的数据有 $$1 \leq N \leq 10^6 , 0 \leq M \leq 3 \cdot 10^6$$，数据有梯度

思路

强连通分量缩点

因为询问一个人只有两种可能，一种此人是杀手，一种此人不是。所以概率即为：$$1- \frac{询问人数}{总人数}$$

那么要求最大概率，就要使询问人数最少。这个时候思路就很明显了，先tarjan缩点，然后求出入度为0的点的个数（必须要询问）。

这个时候还有一种特殊情况，某个入度为0的点，它所连向的所有点得入度都>1，即我们确实是不需要询问这个点就可以知道答案的，所以就减去即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

int n,m,scc,cnt,ans,ind,top;
int head[100005],head2[100005],d[100005];
int low[100005],dfn[100005],st[100005],IC[100005],num[100005];
bool inst[100005],vis[100005];
struct node{int to,next,v;};
node e[300005],ed[300005];

int read()
{
    int sum=0,flag=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')flag=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*flag;
}

void add_edge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}

void add_newedge(int u,int v)
{
    d[v]++;
    ed[++cnt].to=v;ed[cnt].next=head2[u];head2[u]=cnt;
}

void Tarjan(int x)
{
    low[x]=dfn[x]=++ind;
       inst[x]=1;
    st[++top]=x;
    for(int i=head[x];i;i=e[i].next)
        if(!dfn[e[i].to])
        {
            Tarjan(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
        }
        else if(vis[e[i].to])
            low[x]=min(low[x],dfn[e[i].to]);
    if(low[x]==dfn[x])
    {
        int now=0;
        scc++;
        while(x!=now)
        {
            now=st[top];top--;
            IC[now]=scc;
            inst[now]=0;
            num[scc]++;
        } 
    }
}

void rebuild()
{
    cnt=0;
    for(int x=1;x<=n;x++)
    {
        for(int i=head[x];i;i=e[i].next)
            if(IC[x]!=IC[e[i].to]&&!vis[IC[e[i].to]])
                vis[IC[e[i].to]]=1,add_newedge(IC[x],IC[e[i].to]);
        for(int i=head[x];i;i=e[i].next)
            if(IC[x]!=IC[e[i].to])
                vis[IC[e[i].to]]=0;
    }
}

bool judge(int x)
{
    if(d[x]!=0||num[x]!=1)    return 0;
    for(int i=head2[x];i;i=ed[i].next)
        if(d[ed[i].to]==1)    return 0;
    return 1;
}

int main()
{

    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add_edge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])    Tarjan(i);
    rebuild();
    for(int i=1;i<=scc;i++)
        if(!d[i])    ans++;
    for(int i=1;i<=scc;i++)
        if(judge(i))
        {
            ans--;
            break;
        }
    printf("%.6lf",(double)(n-ans)/n);
}

[BZOJ]杀人游戏