Description
一位冷血的Killer潜入 Na-wiat，并假装成Villager。Poli希望能在 N 个人里面，查出谁是Killer。
Poli能够对每一个人进行查证，假如查证的对象是Villager，他会告诉Poli，他认识的人， 谁是Killer， 谁是Villager。
假如查证的对象是Killer， Killer将会把Poli干掉。
现在Poli掌握了每一个人认识谁。
每一个人都有可能是Killer，可看作他们是Killer的概率是相同的。
问：根据最优的情况，保证Poli自身安全并知道谁是Killer的概率最大是多少？
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x）。
Output
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
5 4
1 2
1 3
1 4
1 5
Sample Output
0.800000
HINT
Poli只需要查证 1。假如1是Killer，Poli就会被杀。假如 1不是Killer，他会告诉Poli 2,3,4,5 谁是Killer。
而 1 是Killer的概率是 0.2,所以能知道谁是Killer但没被杀的概率是0.8。对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000
数据已加强！
Source
Solution
首先我们发现如果访问一个强联通分量中一个点 剩下的点噼里啪啦都能访问到了。
所以要缩点。
缩完之后 每一个入度为0的点至少问一次
有种情况会少1：一个size=1，入度=0的强联通分量，如果他所有指向的强联通分量都可以通过访问别的点查证清楚（所有出边的强联通分量的入度>=2），就不用访问他。
记需要访问的点为cnt个
这些点是Killer的概率(Poli GG的概率)是cnt/n，Poli 存活概率1-cnt/n
直接求概率即可。
Code
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
| #include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 300005;
bool insta[maxn];
int n, m, clo, scc, tail, cnte;
int h[maxn], u[maxm], v[maxm];
int rd[maxn], mrd[maxn];
int dfn[maxn], low[maxn], bel[maxn], siz[maxn], sta[maxn];
pair<int, int> e[maxm];
struct edge_t { int to, next; } edge[maxm];
void ins(int x, int y) {
edge[++cnte].to = y;
edge[cnte].next = h[x];
h[x] = cnte;
}
inline int getint() {
int r = 0; bool b = true; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') b = false;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
if (b) return r;
return -r;
}
void tarjan(int now) {
dfn[now] = low[now] = ++clo;
insta[now] = true; sta[++tail] = now;
for (int i = h[now]; i; i = edge[i].next) {
if (!dfn[edge[i].to]) {
tarjan(edge[i].to);
low[now] = min(low[now], low[edge[i].to]);
} else if (insta[edge[i].to])
low[now] = min(low[now], dfn[edge[i].to]);
}
if (dfn[now] == low[now]) {
++scc;
while (true) {
int v = sta[tail--];
insta[v] = false;
bel[v] = scc;
++siz[scc];
if (now == v) break;
}
}
}
int main() {
n = getint(); m = getint();
for (int i = 0; i < m; ++i) {
u[i] = getint();
v[i] = getint();
ins(u[i], v[i]);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
tarjan(i);
for (int i = 0; i < m; ++i)
e[i] = make_pair(bel[u[i]], bel[v[i]]);
sort(e, e + m);
for (int i = 0; i < m; ++i) {
if (e[i].first == e[i].second) continue;
if (e[i].first == e[i+1].first && e[i].second == e[i+1].second) continue;
++rd[e[i].second];
}
for (int i = 1; i <= scc; ++i)
mrd[i] = 1000000007;
for (int i = 0; i < m; ++i)
mrd[e[i].first] = min(mrd[e[i].first], rd[e[i].second]);
int cnt = 0, flag = 0;
for (int i = 1; i <= scc; ++i)
if (rd[i] == 0) {
++cnt;
if (siz[i] == 1 && mrd[i] > 1) flag = 1;
}
double ans = n - cnt + flag;
ans /= n;
printf("%.6lf", ans);
}
|