题目地址：BZOJ：Problem 2438. — [中山市选2011]杀人游戏

题目描述

一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

题意简述

有$n$个人，其中一个人是杀手，警察知道了每个人认识的人的情况，询问一个人，如果他是平民，则会告诉警察他认识的人的身份，如果是杀手警察会被杀死。现在每个人是平民或杀手的概率是相等的，求在最优情况下，警察安全且得到答案的概率。

输入输出格式

输入格式：
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如[一个宽为$w$高为$h$的矩形的面积]）。

输出格式：
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。

输入输出样例

输入样例#1：

5 4
1 2
1 3
1 4
1 5 

输出样例#1：

0.800000 

说明

警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概率是0.8。
对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000

题解

首先，对于一个强连通分量里的点，只需要询问分量中一个不是杀手的人，那么这个分量及它连接的分量的信息都可以安全地知道，因此我们可以考虑缩点然后统计入度为0的点有多少个。
然后你就WA了，这是因为，如果$n-1$个点的信息都知道了，那么第$n$个点不用询问也可以知道，可以少冒一次险问一个未知的人。满足这样条件的点一定是在缩点后的新图中大小为1，入度为0且连接的分量入度都不小于2的这样的分量。
那么假如最后求出需要冒险询问的人数是$x$，那么概率就是$\frac{n-x}{n}$。
复杂度$O(n+m)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <stack>
#include <set>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

const int MAXN = 100005;

int n, m;

std::vector<int> gra[MAXN], gran[MAXN];
int deg[MAXN];

int dfn[MAXN], low[MAXN], clk, sno[MAXN], ssiz[MAXN], scc;
std::stack<int> sta;
bool insta[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    sta.push(u); insta[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        int p; scc++;
        do {
            p = sta.top(); sta.pop();
            insta[p] = false;
            sno[p] = scc;
            ssiz[scc]++;
        } while(p != u);
    }
}

typedef std::pair<int, int> PII;
std::set<PII> edges;

inline bool check(int u) {
    if(deg[u] != 0 || ssiz[u] != 1) return false;
    for(int i = 0; i < gran[u].size(); i++) {
        int v = gran[u][i];
        if(deg[v] < 2) return false;
    }
    return true;
}

int main() {
    n = readint(); m = readint();
    for(int i = 1, u, v; i <= m; i++) {
        u = readint(); v = readint();
        gra[u].push_back(v);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v] && !edges.count(PII(sno[u], sno[v]))) {
                gran[sno[u]].push_back(sno[v]);
                deg[sno[v]]++;
                edges.insert(PII(sno[u], sno[v]));
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= scc; i++) {
        if(!deg[i]) cnt++;
    }
    for(int i = 1; i <= scc; i++) {
        if(check(i)) {
            cnt--; break;
        }
    }
    printf("%.6lf", double(n - cnt) / n);
    return 0;
}