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

Description

一位冷血的杀手潜入Na-wiat,并假装成平民。警察希望能在NN个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人,谁是杀手,谁是平民。假如查证的对象是杀手,杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。

问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?

Input

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

Output

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

Sample Input

1
2
3
4
5
5 4 
1 2
1 3
1 4
1 5

Sample Output

1
0.800000

HINT

警察只需要查证11。假如11是杀手,警察就会被杀。假如11不是杀手,他会告诉警察2,3,4,52,3,4,5谁是杀手。而11是杀手的概率是0.20.2,所以能知道谁是杀手但没被杀的概率是0.80.8

对于100%100\%的数据有1N100000,0M3000001N100000,0M3000001\leq N\leq 100000,0\leq M\leq 3000001\leq N\leq 100000,0\leq M\leq 300000

Solution

根据题意杀手之后一个。
很显然盘问一个人,那么所有这个人能到达的点xx都能被查清楚是杀手还是平民。所以答案就是有多少个入度为00的强连通分量。
不过如果11知道2222知道3344知道33这样的话,如果盘问了11就能确定44了,只要盘问一次。
有两种点不用判断,而且整张图只有一个点可以不用判断。

  • 这个点大小为11,且入度为00,且所有出边指向的点yy的入度都>1>1
  • 这个点大小为11,没有出边,也没有入边,即一个孤立点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 200000, M = 710000;
int n, m;
struct Edge {
int u, v, nxt;
}e[M];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int st[N], top, dfn[N], low[N], num, scc[N], siz[N];
bool vis[N];
int cnt;
void tarjan(int x) {
st[++top] = x;
dfn[x] = low[x] = ++num;
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if(vis[y]) low[x] = min(low[x], dfn[y]);
}
if(dfn[x] == low[x]) {
int y; ++cnt;
do {
y = st[top--];
scc[y] = cnt;
vis[y] = 0;
++siz[cnt];
}while(x != y);
}
}
struct Grao {
struct Edge {
int u, v, nxt;
bool operator <(const Edge &x) const {
if(u == x.u) return v < x.v;
return u < x.u;
}
bool operator == (const Edge &x) const {
return u == x.u && v == x.v;
}
}e[M];
int head[N], en, ind[N], r[N];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y;
}
int solve() {
sort(e + 1,e +1 + en);
en = unique(e + 1, e +1 + en) -e - 1;
for(int i = 1; i <= en; ++i) {
e[i].nxt = head[e[i].u];
head[e[i].u] = i;
++ind[e[i].v];
}
int tot = 0;
for(int i = 1; i <= cnt; ++i) tot += (ind[i] == 0);
for(int i = 1; i <= cnt; ++i) if(siz[i] == 1 && !ind[i]) {
bool fg = 1;
for(int j = head[i]; j; j = e[j].nxt)
if(ind[e[j].v] == 1) fg = 0;
if(fg) return tot - 1;
}
for(int i = 1; i <= cnt; ++i) if(siz[i] == 1 && !head[i] && !ind[i]) return tot - 1;
return tot;
}
}g;

int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y);
}
for(int i = 1; i<= n; ++i) if(!scc[i]) tarjan(i);
for(int i = 1;i <= m; ++i) if(scc[e[i].u] != scc[e[i].v]) g.addedge(scc[e[i].u], scc[e[i].v]);
int x = g.solve();
printf("%.6f\n", (double) (n - x) / n);
return 0;
}