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

2017/03/06

题目

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

代码

容易看出目的是要求最少的查证次数,对整个图求强联通分量缩点, 对于任意一个分量,如果有入度证明这个分量可以被其他分量给解决掉。

如果一个分量没有入度,那么就需要查这个强联通分量上的任意一个点(ans += 1); 如果某个分量只有一个元素也没有入度,可以将 ans - 1,因为可以查完所有人之后推理 这个人的情况。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int PSIZ = 300000 + 1000;
int N, M;

struct tgno {
    int v;
    tgno *n;
} POOL[PSIZ], *Head[PSIZ]; int ppos;

void addEdge(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

int vis[PSIZ], belong[PSIZ], low[PSIZ], dfn[PSIZ], idx;
int stk[PSIZ], stpop, instk[PSIZ];
void dfs(int cur) {
    dfn[cur] = low[cur] = ++idx;
    vis[cur] = 1;
    
    stk[stpop++] = cur; instk[cur] = 1;
    typedef tgno* It;
    
    for(It i=Head[cur];i;i=i->n) {
        if(!vis[i->v]) {
            dfs(i->v);
            low[cur] = min(low[cur], low[i->v]);
        } else if(instk[i->v]) {
            low[cur] = min(low[cur], dfn[i->v]);
        }
    }
    
    if(dfn[cur] == low[cur]) {
        int v = 0;
        while(v != cur) {
            if(stpop == 0) break;
            v = stk[--stpop]; instk[v] = 0; 
            belong[v] = cur;
        }
    }
}

void tarjan() {
    for(int i=1;i<=N;i++) {
        if(!vis[i]) dfs(i);
    }
}

int veccnt[PSIZ], sccout[PSIZ], sccin[PSIZ];
int calc() {
    for(int j=1;j<=N;j++) {
        typedef tgno* It;
        for(It i=Head[j];i;i=i->n) {
            if(belong[j] != belong[i->v]) {
                sccout[belong[j]]++;
                sccin[belong[i->v]]++;
            }
        }
        
        if(belong[j] != j) veccnt[belong[j]] ++;
    }
    
    int s = 0; bool flg = false;
    for(int j=1;j<=N;j++) {
        if(belong[j] == j && !sccin[j]) {
            ++s;
            if(!flg && !veccnt[j]) {
                typedef tgno* It;
                It i = NULL;
                for(i=Head[j];i;i=i->n) {
                    if(sccin[belong[i->v]] == 1) break;
                }
                if(!i) flg = true;
            }
        }
    }
    
    if(flg) s = max(s-1, 0);
    
    return s;
}

int main() {
    scanf("%d %d", &N, &M);
    
    int u, v;
    for(int i=0;i<M;i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    
    tarjan();

    int ans = calc();
    printf("%.6lf", 1.0 - (double(ans) / double(N)));
}