664 字
3 分钟
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缩点 讨论一下入度出度就可以了
#include <cstdio>#include <cstring>#include <queue>#include <stack>using namespace std;struct edge{ int END, next;} v[1000005], E[1000005];int first[100005], Efirst[100005], p, Ep;void add(int a, int c){ v[p].END = c; v[p].next = first[a]; first[a] = p++;}void add1(int a, int c){ E[Ep].END = c; E[Ep].next = Efirst[a]; Efirst[a] = Ep++;}int S[100005];int low[100005], dfsn[100005], Index;bool flag[100005];int T;int belong[100005];stack<int> st;void tarjan(int rt){ low[rt] = dfsn[rt] = ++Index; st.push(rt); flag[rt] = 1; for (int i = first[rt]; i != -1; i = v[i].next) { if (!dfsn[v[i].END]) { tarjan(v[i].END); low[rt] = min(low[rt], low[v[i].END]); } else if (flag[v[i].END]) low[rt] = min(low[rt], dfsn[v[i].END]); } if (dfsn[rt] == low[rt]) { T++; int v; do { v = st.top(); st.pop(); flag[v] = 0; belong[v] = T; S[T]++; } while (dfsn[v] != low[v]); }}int isnroot[100005], ithason[100005];int main(){ memset(first, -1, sizeof(first)); memset(Efirst, -1, sizeof(Efirst)); //freopen("killer.in", "r", stdin); //freopen("killer.out", "w", stdout); int n, m; int s, e; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &s, &e); add(s, e); } for (int i = 1; i <= n; i++) if (!dfsn[i]) tarjan(i); for (int i = 1; i <= n; i++) { for (int j = first[i]; j != -1; j = v[j].next) { if (belong[i] != belong[v[j].END]) { add1(belong[i], belong[v[j].END]); isnroot[belong[v[j].END]]++; ithason[belong[i]]++; } } } int ans = 0; bool flags = 0; for (int i = 1; i <= T; i++) { if (!isnroot[i]) { ans++; if (flags) continue; //if (!ithason[i]) // flags = 1; if (S[i] == 1) { if (!ithason[i]) flags = 1; else { bool e = 0; for (int j = Efirst[i]; j != -1; j = E[j].next) { if (isnroot[E[j].END] == 1) e = 1; } if (!e) flags = 1; } } } } // if (!ans) // ans = 1; if (flags) ans -= 1; printf("%.6lf", (double)(n - ans) / n);}
BZOJ 2438 [中山市选2011] 杀人游戏
https://www.nekomio.com/posts/42/