首先我们考虑一件事:如果存在一个人,使任何一个人都不认识,我们称这种人为“孤独”的人,那么警察只能通过调查他来取得他的身份。

然后对于一个不“孤独”的人,我们发现他们肯定至少被一个那些“孤独”的人直接或间接的认识。

所以我们得出结论:只要统计“孤独”的人的数量即可。


你照着这么做,就可以获得100 mod 10分的好成绩。

那么为什么这不对呢?假设a认识b,就相当于在一个图中从a点向b点连一条边,这样就会造成一个问题:在这张图中会出现环

于是一旦出现环,我们就会发现只要调查环中的一个人,就可以知道环中所有人的身份,但是有可能环中每一个人都不被“孤独”的人间接认识,那么这样,我们可以使用Tarjan缩点,将一个环缩成一个点再进行一开始的算法。


你照着这么做,就可以获得21分的好成绩


那么这次问题又出在哪儿了呢?

我们考虑以下情况

输入数据:

1
100 0

如果按照我们原来的思路,那么我们的程序会输出0,但是实际上可能会怎样呢?

警察来到了一个神奇的地方,这里的人们“鸡犬相闻,而民老死不相往来”(大雾),说白了就是谁都不认识

警察调查了前99个人,发现这99个人里面谁都不是杀手。

正在警察准备调查第100个人时,突然发现只剩一个人了,但是前99个人都不是杀手,所以最后一个人肯定是杀手,不用去调查了

我们瞎算一通,发现出现这种情况的概率是1%,所以我们原来的程序错了!

那怎么办呢?

对于一个入度为0的点,如果它在缩点前是一个点而不是一个环,并且与它相连的点入度都不为1(也就是说不调查这个人不会影响其他人的身份是否明了),那么这个点就可以不调查,但是只允许不调查1个这样的点(原因前面已经讲过了)


你照着这么做,就可以A了。

接下来上代码QAQ


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
#include<bits/stdc++.h>

using namespace std;

#define MAXN 200010
#define MAXM 2000010
int Dfn[MAXN];
int Low[MAXN];
int Stack[MAXN];
int Top = 0;
int Point[MAXN];
bool Ins[MAXN];
int Index;
int Head[MAXN];
int End[MAXM];
int Next[MAXM];
int Head2[MAXN];
int End2[MAXM];
int Next2[MAXM];
bool Used[MAXN];
int Dis[MAXN];
int Degree[MAXN];
int Cnt = 0;
int Cou_p[MAXN];

void Tarjan(int Cur){ // 以烈焰净化一切的环!(大雾)
Dfn[Cur] = Low[Cur] = ++Index;
Ins[Cur] = true;
Stack[++Top] = Cur;
for(int x = Head[Cur]; x != -1; x = Next[x]){
if(Dfn[End[x]] == -1){
Tarjan(End[x]);
if(Low[End[x]] < Low[Cur])
Low[Cur] = Low[End[x]];
}
else if(Ins[End[x]] && Dfn[End[x]] < Low[Cur])
Low[Cur] = Dfn[End[x]];
}
if(Dfn[Cur] == Low[Cur]){
Cnt++;
do{
Cou_p[Cnt]++;
Point[Stack[Top]] = Cnt;
Ins[Stack[Top]] = false;
}while(Stack[Top--] != Cur);
}
}

int Cou = 0;
void Link(int a, int b){ // 连边
Next[++Cou] = Head[a];
Head[a] = Cou;
End[Cou] = b;
}
int Cou2 = 0;
void Relink(int a, int b){ // 重连边
Next2[++Cou2] = Head2[a];
Head2[a] = Cou2;
End2[Cou2] = b;
}

bool Single(int xx){
for(int x = Head2[xx]; x != -1; x = Next2[x])
if(Degree[End2[x]] == 1)
return false;
return true;
}
int main(){
memset(Head, -1, sizeof(Head));
memset(Head2, -1, sizeof(Head2));
memset(Dfn, -1, sizeof(Dfn));
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++){
int a, b;
scanf("%d %d", &a, &b);
Link(a, b);
}
for(int i = 1; i <= n; i++)
if(Dfn[i] == -1)
Tarjan(i);
for(int i = 1; i <= n; i++) // 重建图
for(int x = Head[i]; x != -1; x = Next[x])
if(Point[i] != Point[End[x]]){
Relink(Point[i], Point[End[x]]);
Degree[Point[End[x]]]++;
}
int Ans = 0;
bool Have_one = false;
for(int i = 1; i <= Cnt; i++){
if(!Have_one && Cou_p[i] == 1 && Degree[i] == 0 && Single(i)) // 是否可以使用“排除法”
Have_one = true;
if(Degree[i] == 0)
Ans++;
}
if(Have_one) Ans--;
printf("%.6lf", 1.0 - (double)Ans / (double)n);
}

 评论