首页 > 其他 > 详细

BZOJ2438 [中山市选2011]杀人游戏

时间:2019-06-18 23:53:13      阅读:221      评论:0      收藏:0      [点我收藏+]

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

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 3652  Solved: 1134
[Submit][Status][Discuss]

Description

一位冷血的杀手潜入 Na-wiat,并假装成平民。警察希望能在 N 个人里面,查出谁是杀手。警察能够对每一个人
进行查证,假如查证的对象是平民,他会告诉警察,他认识的人, 谁是杀手, 谁是平民。 假如查证的对象是杀
手, 杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概
率是相同的。问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?

Input

第一行有两个整数 N,M。
接下来有 M 行,每行两个整数 x,y,表示 x 认识 y(y 不一定认识 x,例如胡 锦涛同志) 。

Output

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

Sample Input

5 4
1 2
1 3
1 4
1 5

Sample Output

0.800000

HINT

警察只需要查证 1。假如1是杀手,警察就会被杀。假如 1不是杀手,他会告诉警

察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概

率是0.8。对于 100%的数据有 1≤N ≤  10 0000,0≤M ≤  30 0000


数据已加强!

Source

[Submit][Status][Discuss]
?
HOME Back

题解

看到概率蒙了。分析一下所谓最大概率,是指对于不同决策有不同概率,而最优决策对应的概率是最大的,即最大概率。

参照lych_cys的题解。

显然知道谁是杀手相当于知道所有人的身份。因此题目的答案即在无向图中选择最少的点,使得能遍历到至少(n-1)个点(最后一个点可以推理得到)。设结果为x,则答案为(n-x)/n。

所以就可以用Tarjan找出强联通分量然后缩点,得到的DAG上入度为0的点即所要选择的点。如果存在某个点,这个点所在的强联通分量大小为1而且这个店所有的出边到达的点的入度都>1,那么这个点不选也可以遍历到(n-1)个点,x可以减一。

为什么答案是(n-x)/n?因为杀手随机分布,所以概率即为杀手在剩下的(n-x)个人中的概率。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=1e5+1,M=3e5+1;
int n,m,low[N],dfn[N],num;
int head[N],edge[M],next[M],tot;
int st[N],top,c[N],cnt[N],scc;
bool ins[N],v[N];
int hc[N],ec[M],nc[M],tc,deg[N];

il void add(int x,int y){
    edge[++tot]=y,next[tot]=head[x],head[x]=tot;
}
il void add_c(int x,int y){
    ec[++tc]=y,nc[tc]=hc[x],hc[x]=tc,++deg[y];
}
void tarjan(int x){
    low[x]=dfn[x]=++num;
    st[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=next[i]){
        int y=edge[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        ++scc;
        int y;
        do{
            y=st[top--],ins[y]=0;
            c[y]=scc,++cnt[scc];
        }while(x!=y);
    }
}
bool pd(int x){
    if(deg[x]||cnt[x]!=1) return 0;
    for(int i=hc[x];i;i=nc[i])
        if(deg[ec[i]]==1) return 0;
    return 1;
}
int main(){
    read(n),read(m);
    for(int x,y;m--;){
        read(x),read(y);
        add(x,y);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i]) tarjan(i);
    for(int x=1;x<=n;++x){
        for(int i=head[x];i;i=next[i]){
            int y=edge[i];
            if(c[x]==c[y]||v[c[y]]) continue;
            add_c(c[x],c[y]),v[c[y]]=1;
        }
        for(int i=head[x];i;i=next[i]) v[c[edge[i]]]=0;
    }
    int ans=0;
    for(int i=1;i<=scc;++i)
        if(!deg[i]) ++ans;
    for(int i=1;i<=scc;++i)
        if(pd(i)) {--ans;break;}
    printf("%.6lf\n",(double)(n-ans)/n);
    return 0;
}

BZOJ2438 [中山市选2011]杀人游戏

原文:https://www.cnblogs.com/autoint/p/11048252.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!