【BZOJ2438】 [中山市选2011]杀人游戏 tarjan强连通分量+缩点-布布扣-bubuko.com

Description

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

Input

第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如hjt同志）。

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

数据已加强！

tarjan求强连通+缩点后，统计入度为0的点，最后特判一下（并不知道为什么）。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <stack>
 6 #include <cmath>
 7 #define N 100010
 8 #define M 300010
 9 using namespace std;
10 stack<int> q; 
11 struct data1{int next,p;}e[M],e1[M];
12 int n,m,scc,ans,cnt;
13 int head[N],head1[N],h[N],vis[N],dfn[N],low[N],rsum[N],belong[N];
14 bool inq[M];
15 void se1(int x,int y){h[y]++;cnt++; e1[cnt].next=head1[x]; head1[x]=cnt; e1[cnt].p=y;}
16 void se(int x,int y){cnt++; e[cnt].next=head[x]; head[x]=cnt; e[cnt].p=y;}
17 void tarjan(int x)
18 {
19     vis[x]=inq[x]=1;
20     dfn[x]=low[x]=++cnt;
21     q.push(x);
22     for (int i=head[x];i!=-1;i=e[i].next)
23     {
24         if (!vis[e[i].p])
25         {
26             tarjan(e[i].p);
27             low[x]=min(low[x],low[e[i].p]);
28         }
29         else if (inq[e[i].p])   low[x]=min(low[x],low[e[i].p]);         
30     }
31     if (low[x]==dfn[x])
32     {
33         int now;
34         scc++;
35         while (now!=x)
36         {
37             now=q.top();q.pop();
38             belong[now]=scc;
39             inq[now]=0;
40             ++rsum[scc];
41         }
42     }
43 }
44 void part1_tarjan()
45 {
46     cnt=0;
47     for (int i=1;i<=n;i++)
48         if (!vis[i])
49             tarjan(i);
50 }
51 void part2_shr_point()
52 {
53     cnt=0;
54     for (int i=1;i<=n;i++)
55         for (int t=head[i];t!=-1;t=e[t].next)
56         {
57             if (belong[i]!=belong[e[t].p])
58                 se1(belong[i],belong[e[t].p]);
59         }
60 }
61 bool ju(int x)
62 {
63     cnt=0;
64     if (h[x] || rsum[x]!=1) return 0;
65     for (int i=head1[x];i!=-1;i=e1[i].next)
66         if (h[e1[i].p]==1)  return 0;
67     return 1;
68 }
69 void part3_judge()
70 {
71     cnt=0;
72     for (int i=1;i<=scc;i++)
73     if (!h[i])  ans++;
74     for (int i=1;i<=scc;i++)
75     if (ju(i))  {ans--;return;}
76 }
77 int main()
78 {
79     memset(e,-1,sizeof(e));
80     memset(e1,-1,sizeof(e1));
81     memset(head1,-1,sizeof(head1));
82     memset(head,-1,sizeof(head));
83     scanf("%d%d",&n,&m);
84     for (int i=1;i<=m;i++)
85     {
86         int x,y;
87         scanf("%d%d",&x,&y);
88         se(x,y);
89     }
90     part1_tarjan();
91     part2_shr_point();
92     part3_judge();
93     printf("%.6lf",(double)(n-ans)/n);
94     return 0;
95 }

View Code

【BZOJ2438】 [中山市选2011]杀人游戏 tarjan强连通分量+缩点

原文：http://www.cnblogs.com/DMoon/p/5255202.html