【bzoj2438】[中山市选2011]杀人游戏

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

题解

在一个强联通中，可以一步一步推出每个人，所以只需要知道一个人就可以了，然后就是入度为0的点有关了。

ans=入度为0的连通块个数

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn=1e5+,maxm=3e5+;

 int pre[maxn],low[maxn],scc[maxn],clock,cnt;

 int head[maxn],f[maxm],e[maxm],nxt[maxm],k;

 int adde(int u,int v){

     e[++k]=v,f[k]=u;

     nxt[k]=head[u],head[u]=k;

 }

 int n,m,r[maxn],a[maxn],t;

 int size[maxn],num[maxn];

 int dfs(int u){

     pre[u]=low[u]=++clock;

     a[++t]=u;

     for(int i=head[u];i;i=nxt[i]){

         int v=e[i];

         if(!pre[v]){

             dfs(v);

             low[u]=min(low[u],low[v]);

         }

         else if(!scc[v]){

             low[u]=min(low[u],pre[v]);

         }

     }

     if(low[u]==pre[u]){

         num[++cnt]=u;

         while(t){

             scc[a[t]]=cnt;

             size[cnt]++;

             if(a[t--]==u) break;

         }

     }

 }

 int pd(int x){

     int u=num[x];

     for(int i=head[u];i;i=nxt[i])

         if(r[scc[e[i]]]==) return ;

     return ;

 }

 int main(){

     scanf("%d%d",&n,&m);

     int u,v;

     for(int i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         adde(u,v);

     }

     for(int i=;i<=n;i++)

         if(!pre[i]) dfs(i);

     for(int i=;i<=k;i++)

         if(scc[f[i]]!=scc[e[i]]) r[scc[e[i]]]++;

     int ans=;

     for(int i=;i<=cnt;i++)

         if(!r[i]) ans++;

     for(int i=;i<=cnt;i++)

         if(size[i]==&&!r[i]&&pd(i)){

             ans--;

             break;

         }

     printf("%.6lf",(double)(n-ans)/n);

     return ;

 }

杀人游戏

bzoj2438 杀人游戏 Tarjan强联通