[中山市选2011]杀人游戏

发表于 | 分类于

题目

一位冷血的杀手潜入 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

OUTPUT

0.800000

解题报告

考试时没想出来，随便打的输出样例- -
正解：
警察只有两种结果——查到犯人或者死，而死一定是包含在“调查未知身份的人”，也就是说调查未知身份的人越多，死亡概率越高，所以我们要求警察如何尽可能少调查未知身份的人
那么问题就很简单了，我们发现对于一个强连通分量，我们可以把他们看作一个人，因为调查了其中一个，剩余的都可以安全到达（正确性显然，因为你只要安全调查了其中的一个人，你就可以通过每次确认安全的人从而调查整个强连通分量），那么我们就可以tarjan一下，那么我们调查的对象就为缩点后入度为0的点（因为你无法从其他点通向这个点，你只能通过调查其中一个未知身份的人来调查整个强连通分量，如果警察RP不好，第一个选中杀手，警察就GG了），所以调查的未知身份的人数就是这些点的数量。
坑点：
存在这样一种情况，至少有一个点，且只有一个人，而且没人认识他，他也不认识别人，或者他认识的每个人都能被除他以外的其他人所认识（即入度>1），那么我们调查完其他人后，他就是杀手（正确性显然，对于第一种情况，考虑n=1就行，对于第二种情况，他认识的人已经被调查过了，而其他人自然也被调查过，那么他自己就是剩下未调查的唯一可能的杀手）。
那么如何处理呢？
进行特判，顺便dfs一下，判断是否属于这种情况就可以啦

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
100
101
102
103
104
105
106
107
108
109
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
struct edge{
    int s,e,n;
}a[300001],b[100001];
int pre[100001],tot;
int adj[100001],ttt;
inline void insert(int s,int e){
    a[++tot].s=s;
    a[tot].e=e;
    a[tot].n=pre[s];
    pre[s]=tot;
}
inline void add(int s,int e){
    b[++ttt].s=s;
    b[ttt].e=e;
    b[ttt].n=adj[s];
    adj[s]=ttt;
}
int n,m;
int stack[100001],top;
int cnt,low[100001],dfn[100001],bl[100001],qlt;
bool vis[100001];
int size[100001];
inline int my_min(int a,int b){
    return a<b?a:b;
}
inline void tarjan(int u){
    cnt++;
    vis[u]=1;
    low[u]=dfn[u]=cnt;
    stack[++top]=u;
    for(int i=pre[u];i!=-1;i=a[i].n){
        int e(a[i].e);
        if(!dfn[e]){
            tarjan(e);
            low[u]=my_min(low[u],low[e]);
        }
        else
            if(vis[e])
                low[u]=my_min(low[u],dfn[e]);
    }
    if(low[u]==dfn[u]){
        int tmp;
        qlt++;
        while(1){
            tmp=stack[top--];
            bl[tmp]=qlt;
            vis[tmp]=0;
            if(tmp==u)
                break;
        }
    }
}
bool flag[100001];
inline void uni(int u){//坑点处理dfs
    for(int i=adj[u];i!=-1;i=b[i].n){
        int e(b[i].e);
        if(!vis[e]){
            vis[e]=1;
            uni(e);
            size[u]+=size[e];
        }
    }
}
int ans(0);
int ind[100001];
int main(){
//  freopen("killer.in","r",stdin);
//  freopen("killer.out","w",stdout);
    memset(pre,-1,sizeof(pre));
    memset(adj,-1,sizeof(adj));
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x(read()),y(read());
        insert(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        size[bl[i]]++;
    for(int i=1;i<=m;i++){
        int s(a[i].s),e(a[i].e);
        if(bl[s]!=bl[e])
            add(bl[s],bl[e]),ind[bl[e]]++;
    }
    for(int i=1;i<=qlt;i++)
        if(!ind[i]){//坑点特判
            uni(i);
            if(size[i]==1){
                ans=-1;
                break;
            }
        }
    for(int i=1;i<=qlt;i++)
        if(ind[i]==0)
            ans++;
    printf("%.6lf",(double)(n-ans)/(double)n);
}

哀民生之多艰啊- -