问题 C: [中山市选2011]杀人游戏
时间限制: 1 Sec 内存限制: 128 MB 提交: 64 解决: 33 [ ][ ][ ]题目描述
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，
查出谁是杀手。 警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他 认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。 现在警察掌握了每一个人认识谁。 每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。 问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多 少？输入
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如***同志） 。输出
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
样例输入
5 4 1 2 1 3 1 4 1 5
样例输出
0.800000
提示
警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警
察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概 率是0.8。对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000数据已加强！（→ _→ ）
其他大佬都80行，就我一百多行。
如果一个人被审查了，那就知道了所有联系他的人身份，搜他们就是安全的，不会死。
注意：要缩点，防止那种你认识我，我也认识你那种。。。
更加注意：如果一个人是孤立的，就剩他一个没搜时就确定他的身份了，
这个人要么不认识任何人，要么他认识的别人都认识。。（说白了就是不用通过他得知别人的身份）
#include#include #include #include #include #define N 100000using namespace std;int n,m,adj[N+5],e,E;int belong[N+5],cnt,in[N+5],p=0,id[N+5],out[N+5];int zhan[N+5],head,dfn[N+5],low[N+5],hh,vis[N+5],inzhan[N+5];int A[N+5];double ans;struct node { int u,v,next;} lu[N*3+5],b[N*3+5];void add(int u,int v){ lu[++e].v=v;lu[e].u=u;lu[e].next=adj[u];adj[u]=e;}void add2(int u,int v){ b[E++].v=v;b[E].next=A[u];A[u]=E;}int check(int x){ for(int i=A[x];i;i=b[i].next) { int k=b[i].v; if(in[k]==1) return 0; } return 1;}int read(){ int sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();} while(x>='0'&&x<='9')sum=sum*10+x-'0',x=getchar(); return sum*f;}void dfs(int x){ zhan[++head]=x;inzhan[x]=1; vis[x]=1; low[x]=dfn[x]=++hh; for(int i=adj[x];i!=-1;i=lu[i].next) { int k=lu[i].v; if(!vis[k]) { dfs(k); low[x]=min(low[x],low[k]); } else if(inzhan[k]) low[x]=min(low[x],dfn[k]); } if(dfn[x]==low[x]) { int s=0,temp; cnt++; while(1) { temp=zhan[head--]; inzhan[temp]=0; belong[temp]=cnt; s++; if(temp==x)break; } id[cnt]=s; }}int main(){ //freopen("killer.in","r",stdin); //freopen("killer.out","w",stdout); memset(adj,-1,sizeof(adj)); n=read();m=read(); int x,y; for(int i=1;i<=m;i++) { x=read();y=read(); add(x,y); } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); for(int i=1;i<=m;i++) if(belong[lu[i].u]!=belong[lu[i].v]) { in[belong[lu[i].v]]++,out[belong[lu[i].u]]++; add2(belong[lu[i].u],belong[lu[i].v]); } for(int i=1;i<=cnt;i++) if(!in[i]) ans++; for(int i=1;i<=cnt;i++) if(id[i]==1&&!in[i]&&(!out[i]||check(i))) p=1; if(p==1)ans--; ans=(double)(n-ans)/n; printf("%.6lf",ans);}