bzoj2438 杀人游戏

bzoj2438 杀人游戏

​​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

数据已加强！

根据题目的意思就是我们要 询问最少的人 知道其中n-1个人的情况

如果一圈人互相知道，我们就给他缩点

然后我们寻找没有入度的点 每个缩点之后入度为0的点，都是我们要调查的点

有一种特殊情况 我们 有可能有一个人 没人认识他 或者他认识的人 我们通过其他人都可以了解到

那么这个人也是不用调查的

这题其实理解题意很关键

一开始我 难以理解题意 不知道这个概率如何求 取决于 警察可能问一个人 然后他的下场不是死就是活着 死亡=调查的未知身份的人数/总人数

#include#include#define N 110000#define M 330000using namespace std;stack q;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,next;}data[M],data1[M];int dfn[N],low[N],num,h[N],h1[N],s,b[N],size[N];bool stackf[N];void tarjan(int x){ dfn[x]=low[x]=++num;stackf[x]=true;q.push(x); for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if (stackf[y]) low[x]=min(low[x],dfn[y]); } if (dfn[x]==low[x]){ s++;int y; do { y=q.top();q.pop();stackf[y]=false;b[y]=s;size[s]++; }while (y!=x); }}int n,m,in[N];bool visit[N];inline bool judge(int x){ for (int i=h1[x];i;i=data1[i].next) if (in[data1[i].y]==1) return false; return true;}int main(){ //freopen("bzoj2438.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; }num=0; for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i);num=0; for (int i=1;i<=m;++i){ for (int j=h[i];j;j=data[j].next){ int y=data[j].y; if (b[i]!=b[y]) if (!visit[b[y]]){visit[b[y]]=true; data1[++num].y=b[y],data1[num].next=h1[b[i]],h1[b[i]]=num;in[b[y]]++; } } for (int j=h1[b[i]];j;j=data1[j].next) visit[data1[j].y]=false; } double ans=0; for (int i=1;i<=s;++i) if (!in[i]) ++ans; for (int i=1;i<=s;++i) if (size[i]==1&&!in[i]&&judge(i)) {ans--;break;} printf("%.6lf",(n-ans)/n); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。