「BZOJ 2438」杀人游戏 - 强连通分量

发表于 | 分类于

一位杀手潜入假装成平民。警察希望能在 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。

现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。

根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

链接

BZOJ 2438

题解

如果一些人在一个强连通分量中，那么这些人中只需要查证一个人。

缩点后，统计有多少入度为零的点，查证这些点一定不会漏掉。

考虑这样一种特殊情况：只有一个人，这个人一定是杀手，即不需要查证任何人。

更普遍的，每一个入度为零一个人的单点（必须是一个人不能是一群人），对于其连接的所有点，这些点的入度如果都不为 ，则这个人可以不需要查证。查证其它所有人后，他认识的人也都被查证过，只剩他一个人不需要查证即知道身份。

代码

#include <cstdio>
#include <algorithm>
#include <stack>

const int MAXN = 100000;

struct Node;
struct Edge;
struct SCC;

struct Node {
    Edge *e, *in, *c;
    bool visited, pushed, inStack;
    int dfn, low, inDegree;
    SCC *scc;
} N[MAXN];

struct Edge {
    Node *s, *t;
    Edge *next;

    Edge(Node *s, Node *t) : s(s), t(t), next(s->e) {}
};

struct SCC {
    Node v;
    int s;
} S[MAXN];

inline void addEdge(const int s, const int t) {
    N[s].e = new Edge(&N[s], &N[t]);
}

int n, m;

inline int tarjan() {
    int time = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        if (N[i].visited) continue;

        std::stack<Node *> s, t;
        s.push(&N[i]);
        N[i].pushed = true;

        while (!s.empty()) {
            Node *v = s.top();

            if (!v->visited) {
                v->visited = true;
                v->c = v->e;
                v->dfn = v->low = time++;
                v->inStack = true;
                t.push(v);
            }

            if (v->c) {
                if (v->c->t->inStack) v->low = std::min(v->low, v->c->t->dfn);
                else if (v->c->t->pushed == false) s.push(v->c->t), v->c->t->pushed = true, v->c->t->in = v->c;
                v->c = v->c->next;
            } else {
                if (v->dfn == v->low) {
                    Node *u;
                    SCC *scc = &S[cnt++];
                    do {
                        u = t.top();
                        t.pop();
                        u->inStack = false;
                        u->scc = scc;
                        u->scc->s++;
                    } while (u != v);
                }

                if (v->in) v->in->s->low = std::min(v->in->s->low, v->low);

                s.pop();
            }
        }
    }

    return cnt;
}

inline void contract() {
    for (int i = 0; i < n; i++) {
        for (Edge *e = N[i].e; e; e = e->next) {
            if (e->s->scc != e->t->scc) {
                e->s->scc->v.e = new Edge(&e->s->scc->v, &e->t->scc->v);
                e->t->scc->v.inDegree++;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int s, t;
        scanf("%d %d", &s, &t), s--, t--;
        addEdge(s, t);
    }

    int cnt = tarjan();
    contract();

    int k = 0;
    for (int i = 0; i < cnt; i++) {
        if (S[i].v.inDegree == 0) k++;
    }

    for (int i = 0; i < cnt; i++) {
        if (S[i].v.inDegree == 0 && S[i].s == 1) {
            bool flag = false;
            for (Edge *e = S[i].v.e; e; e = e->next) {
                if (e->t->inDegree <= 1) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                k--;
                break;
            }
        }
    }

    printf("%.6lf\n", static_cast<double>(n - k) / n);

    return 0;
}