Luogu4819 [中山市选]杀人游戏

发布于 2019-10-13  201 次阅读


Link

题解

这道题相信大家都会做,实在Easy

首先容易想到用Tarjan缩点,因为加入原图上存在一个环,那么查询这个换上的杀手信息得到的结果集合是相同的,所以我们缩完点之后就可以通过原图环上的一个点查询这个环上所有的信息。

考虑到这里,还要考虑到一个特殊情况。例如,在通过查完一些点的信息得到了 n - 1 人是平民以后,剩下的那个人肯定是凶手,便可以减少一次询问,所以我们要在原图中找到一个大小为一且入度为0的点,如果存在一个这样的点,那么我们便可以减少一次询问。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100000 + 5;
const int SIZE_EDGE = 300000 + 5;

int n, m, num, ind, tot, flag;
int head[SIZE], x[SIZE_EDGE], y[SIZE_EDGE], dfn[SIZE], low[SIZE], in[SIZE], Size[SIZE], deg[SIZE], scc[SIZE];

struct node {
    int to, Next;
} edge[SIZE_EDGE];

std::stack < int > s;

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int u)
{
    dfn[u] = low[u] = ++ind, in[u] = 1;
    s.push(u);
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[u] = std::min(low[u], low[v]);
        }
        else if (in[v]) low[u] = std::min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++tot;
        while (s.top() != u) {
            scc[s.top()] = tot, Size[tot]++, in[s.top()] = 0;
            s.pop();
        }
        scc[s.top()] = tot, Size[tot]++, in[s.top()] = 0;
        s.pop();
    }
}

int main()
{
    int u, v;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        x[i] = read(), y[i] = read();
        Addedge(x[i], y[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) DFS(i);
    }
    num = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, 0, sizeof(head));
    for (int i = 1; i <= m; i++) {
        if (scc[x[i]] != scc[y[i]]) {
            deg[scc[y[i]]]++;
            Addedge(scc[x[i]], scc[y[i]]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= tot; i++) {
        if (!flag && !deg[i] && Size[i] == 1) {
            int tag = 0;
            for (int k = head[i]; k; k = edge[k].Next) {
                v = edge[k].to;
                if (deg[v] == 1) tag = 1;
            }
            if (!tag) flag = 1;
        }
        if (!deg[i]) ans++;
    }
    if (flag) ans--;
    printf("%.6lf", 1.0 - (double) ans / (double) n);
    return 0;
}

朴实沉毅