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

#概率 #tarjan
Published on 2016-06-23

题目地址

描述

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

分析

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

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

实际上，我们只需要知道 n−1n - 1 个人的身份，就可以知道所有人的身份了，假如有一个入度为 00 的点只代表一个原图的点，而且它连向所有的点的入度都大于 11，那么这个点是无需询问的，只需询问 x−1x - 1 个点，就可以确定 n−1n - 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;
}
BZOJ 3887 - [Usaco2015 Jan]Grass Cownoisseur