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

Published on 2016-06-23

题目地址

描述

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

分析

几个细节,认识具有传递性,xx 认识 yyyy 认识 zz,那么 xx 也认识 zz
每个人是杀手的概率是 1n\frac 1 n,所以如果询问 kk 个人,那么被杀的概率就是 kn\frac k n,所以我们的目标是询问尽量少的人 kk,来保证能确定杀手。

可以发现,在一个强连通分量里面的点,只需要询问一个就可以知道所有的人,所以我们第一步用 tarjan 将强连通分量缩成点。
这样我们得到了一个 DAG,我们要选择尽量少的点,使得从这些点出发,能到达所有的点,显然选所有入度为 00 的点最优,假设入度 00 的点的数量为 xx,那么答案为 nxn\frac {n - x} n

实际上,我们只需要知道 n1n - 1 个人的身份,就可以知道所有人的身份了,假如有一个入度为 00 的点只代表一个原图的点,而且它连向所有的点的入度都大于 11,那么这个点是无需询问的,只需询问 x1x - 1 个点,就可以确定 n1n - 1 个人的身份,也就确定了这个点的身份,所以要特判掉这种情况。

没做出来的原因:对概率的恐惧,没有分析出询问 xx 个人,被杀的概率就是 xn\frac x n 这一极其简单的性质。
总结:对不熟的东西不要恐惧,要根据已经掌握的知识,将问题转化,而不是抱着“我没学过理应做不出来”的心态。

代码

//  Created by Sengxian on 6/23/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2438 tarjan + 概率
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3;
vector<int> G[maxn], nG[maxn];
int n, m, dfn[maxn], sccno[maxn], scc_sz[maxn], timestamp = 0, scc_cnt = 0;
int in[maxn];

stack<int> stk;
int dfs(int u) {
    int low = dfn[u] = ++timestamp;
    stk.push(u);
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (!dfn[v]) low = min(low, dfs(v));
        else if (!sccno[v]) low = min(low, dfn[v]);
    }
    if (low == dfn[u]) {
        scc_cnt++;
        do {
            int v = stk.top(); stk.pop();
            scc_sz[scc_cnt]++;
            sccno[v] = scc_cnt;
            if (u == v) break;
        } while (!stk.empty());
    }
    return low;
}


char str[maxn];
int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    int n = ReadInt(), m = ReadInt();
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t);
    }
    timestamp = 0, scc_cnt = 0;
    memset(dfn, 0, sizeof dfn);
    for (int i = 0; i < n; ++i) if (!dfn[i]) dfs(i);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < (int)G[i].size(); ++j) {
            int v = G[i][j];
            if (sccno[i] != sccno[v]) nG[sccno[i]].push_back(sccno[v]), in[sccno[v]]++;
        }
    int cnt = 0;
    for (int i = 1; i <= scc_cnt; ++i) if (in[i] == 0) cnt++;
    for (int i = 1; i <= scc_cnt; ++i)
        if (scc_sz[i] == 1 && in[i] == 0) {
            bool flag = true;
            for (int j = 0; j < (int)nG[i].size(); ++j)
                if (in[nG[i][j]] <= 1) {flag = false; break;}
            if (flag) {cnt--; break;}
        }
    printf("%.6lf\n", (double)(n - cnt) / n);
    return 0;
}