Skip to content

14120: 【原4120】天使的入侵

题目

题目描述

author: Ca. 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4120

Description

天使们又开发了新的技能simulation,现在她绑架了战线中的一个成员,伪装成战线成员混入了战线,由理子想排查出哪一个成员是天使假扮的,这个任务就交给音无了,音无听说你编程水平高超,就把找寻最优策略的事交给了你。 战线中的关系可以用一个有向图来描述,边a->b表示盘问了a后如果a是好人那么会告诉你b是不是天使假扮的。 但是如果你盘问了天使假扮的成员的话就会被天使戳了,虽然音无被戳没啥事,但是还是很疼啊,因此请你求出如果采取最优策略的话最坏情况下音无知道哪个人是天使并且不被戳的概率是多少?

Input Format

第一行两个整数n,m,战线人数和边数。 以下m行,每行2个整数a,b,编号为a的人向编号为b的人连一条有向边。

Output Format

一行一个实数,保留六位小数,(注意保留是指截尾操作,即0.66666666666输出为0.666666),表示最大概率。

Sample Input1

5 4
1 2
1 3
1 4
1 5

Sample Output1

0.800000

Sample Input2

5 0

Sample Output2

0.200000

Data Range

20%的数据满足1<=n<=10,0<=m<=10; 50%的数据满足1<=n<=1000,0<=m<=2000; 100%的数据满足1<=n<=100000,0<=m<=300000。

Hint

如果你的询问策略中存在一个一定要询问其本人才能确定身份的成员,而你已经通过询问确定了其他所有成员的身份,在这种情况下你只需要采用排除法就可以得到这位成员的身份,而不用冒着被戳的风险再进行一次询问。

zqy2018's solution

/*
    Hint: use Tarjan to find all SCCs and count the number of SCCs with zero in-degree
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int to[300005], nxt[300005], at[100005] = {0}, cnt = 0;
int ind[100005] = {0}, outd[100005] = {0}, siz[100005] = {0}, tot = 0;
int rep[100005] = {0};
int dfn[100005] = {0}, low[100005], D = 0;
int stk[100005], tp = 0;
bool in[100005] = {0};
void tarjan(int cur){
    dfn[cur] = low[cur] = ++D;
    stk[tp++] = cur, in[cur] = true;
    for (int i = at[cur]; i; i = nxt[i]){
        int v = to[i];
        if (!dfn[v])
            tarjan(v), low[cur] = min(low[cur], low[v]);
        else if (in[v])
            low[cur] = min(low[cur], dfn[v]);
    }
    if (low[cur] == dfn[cur]){
        int scc_rep = ++tot;
        do{
            --tp;
            int u = stk[tp];
            in[u] = false;
            rep[u] = scc_rep;
            ++siz[scc_rep];
            for (int i = at[u]; i; i = nxt[i])
                if (rep[to[i]] != scc_rep)
                    ++ind[rep[to[i]]], ++outd[scc_rep];
        }while (stk[tp] != cur);
    }
}
void init(){
    n = read(), m = read();
    for (int i = 1; i <= m; ++i){
        int u = read(), v = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
}
void solve(){
    int cnt1 = 0, cntt = 0;
    for (int i = 1; i <= tot; ++i){
        if (ind[i]) continue;
        // cout << i << endl;
        ++cntt;
        if (!outd[i] && siz[i] == 1) ++cnt1;
    }
    int ans = cntt - min(cnt1, 1);
    char s[10];
    sprintf(s, "%.7f", 1.0 * (n - ans) / n);
    s[8] = '\n';
    printf("%s", s);
}
int main(){
    init();
    solve();
    return 0;
}