BZOJ 2438 [中山市选2011] 杀人游戏

Description#

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

Sample Output#

0.800000

HINT#

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

对于 100%的数据有 1≤N ≤100000,0≤M ≤300000 数据已加强！

题解#

Tarjan缩点讨论一下入度出度就可以了

1
#include <cstdio>
2
#include <cstring>
3
#include <queue>
4
#include <stack>
5
using namespace std;
6
struct edge
7
{
8
    int END, next;
9
} v[1000005], E[1000005];
10
int first[100005], Efirst[100005], p, Ep;
11
void add(int a, int c)
12
{
13
    v[p].END = c;
14
    v[p].next = first[a];
15
    first[a] = p++;
16
}
17
void add1(int a, int c)
18
{
19
    E[Ep].END = c;
20
    E[Ep].next = Efirst[a];
21
    Efirst[a] = Ep++;
22
}
23
int S[100005];
24
int low[100005], dfsn[100005], Index;
25
bool flag[100005];
26
int T;
27
int belong[100005];
28
stack<int> st;
29
void tarjan(int rt)
30
{
31
    low[rt] = dfsn[rt] = ++Index;
32
    st.push(rt);
33
    flag[rt] = 1;
34
    for (int i = first[rt]; i != -1; i = v[i].next)
35
    {
36
        if (!dfsn[v[i].END])
37
        {
38
            tarjan(v[i].END);
39
            low[rt] = min(low[rt], low[v[i].END]);
40
        }
41
        else if (flag[v[i].END])
42
            low[rt] = min(low[rt], dfsn[v[i].END]);
43
    }
44
    if (dfsn[rt] == low[rt])
45
    {
46
        T++;
47
        int v;
48
        do
49
        {
50
            v = st.top();
51
            st.pop();
52
            flag[v] = 0;
53
            belong[v] = T;
54
            S[T]++;
55
        } while (dfsn[v] != low[v]);
56
    }
57
}
58
int isnroot[100005], ithason[100005];
59
int main()
60
{
61
    memset(first, -1, sizeof(first));
62
    memset(Efirst, -1, sizeof(Efirst));
63
    //freopen("killer.in", "r", stdin);
64
    //freopen("killer.out", "w", stdout);
65
    int n, m;
66
    int s, e;
67
    scanf("%d%d", &n, &m);
68
    for (int i = 1; i <= m; i++)
69
    {
70
        scanf("%d%d", &s, &e);
71
        add(s, e);
72
    }
73
    for (int i = 1; i <= n; i++)
74
        if (!dfsn[i])
75
            tarjan(i);
76
    for (int i = 1; i <= n; i++)
77
    {
78
        for (int j = first[i]; j != -1; j = v[j].next)
79
        {
80
            if (belong[i] != belong[v[j].END])
81
            {
82
                add1(belong[i], belong[v[j].END]);
83
                isnroot[belong[v[j].END]]++;
84
                ithason[belong[i]]++;
85
            }
86
        }
87
    }
88
    int ans = 0;
89
    bool flags = 0;
90
    for (int i = 1; i <= T; i++)
91
    {
92
        if (!isnroot[i])
93
        {
94
            ans++;
95
            if (flags)
96
                continue;
97
            //if (!ithason[i])
98
            //    flags = 1;
99
            if (S[i] == 1)
100
            {
101
                if (!ithason[i])
102
                    flags = 1;
103
                else
104
                {
105
                    bool e = 0;
106
                    for (int j = Efirst[i]; j != -1; j = E[j].next)
107
                    {
108
                        if (isnroot[E[j].END] == 1)
109
                            e = 1;
110
                    }
111
                    if (!e)
112
                        flags = 1;
113
                }
114
            }
115
        }
116
    }
117
    // if (!ans)
118
    //     ans = 1;
119
    if (flags)
120
        ans -= 1;
121
    printf("%.6lf", (double)(n - ans) / n);
122
}