[Solution][Graph Theory][SCC]BZOJ 2438 杀人游戏

【题目】

戳这里

【思路】

考虑SCC,如果SCC中的一个点被询问过,那么整个SCC中的所有点的情况就都知道了。

想要知道警察最终活下来的(最大)几率,就可以用1减去警察死亡的(最小)概率。

首先进行强连通分量缩点,在新的DAG中入度为0的点显然可以用较小的死亡几率确定更多的信息,确认所有的入度为0的点显然就是最优决策。

所以满足条件的最小死亡几率就是在这些SCC中随机选一个点躺枪的概率和。即.

不过还有一点需要注意,我们并不一定需要询问所有的入度为0的点,如果所有剩下的点都已经被直接或间接地访问过了,显然我们不必再去询问这最后一个点也能得出答案。

所以如果有入度为0的点强连通分量度为1(只剩下这最后一个点时),可以减少一个访问量。

【代码】

#include<cstdio>
#include<cstring>
inline int _min(int a , int b)
{
    return a < b ? a : b;
}
const int N = 100001;
const int M = 300100;
int head[N] , next[M] , end[M];
void addedge(int a , int b)
{
    static int q = 1;
    end[q] = b;
    next[q] = head[a];
    head[a] = q++;
}
int belong[N] , size_scc[N] , now , dfn[N] , low[N] , time_clock;
bool ext[N] , instack[N];
int stack[N] , top;
inline void dfs(int x)
{
    int j;
    dfn[x] = low[x] = ++time_clock;
    stack[++top] = x;
    instack[x] = 1;
    ext[x] = 1;
    for(j = head[x] ; j ; j = next[j])
    {
        if (!ext[end[j]])
        {
            dfs(end[j]);
            low[x] = _min(low[x] , low[end[j]]);
        }
        else if (instack[end[j]])
            low[x] = _min(low[x] , dfn[end[j]]);
    }
    if (low[x] == dfn[x])
    {
        ++now;
        while(1)
        {
            //i = S.top();
            belong[stack[top]] = now;
            instack[stack[top]] = 0;
            ++size_scc[now];
            if (dfn[stack[top]] == low[stack[top]])
            {
                --top;
                break;
            }
            --top;
        }
    }
}
int in[N];
int main()
{
    //freopen("fig8.in" , "r" , stdin);
    int n , m;
    scanf("%d%d" , &n , &m);
    int a , b;
    register int i , j;
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d" , &a , &b);
        addedge(a , b);
    }
    for(i = 1 ; i <= n ; ++i)
        if (!ext[i])
            dfs(i);
    for(i = 1 ; i <= n ; ++i)
    for(j = head[i] ; j ; j = next[j])
        if (belong[i] != belong[end[j]])
            ++in[belong[end[j]]];
    int ans = 0;
    for(i = 1 ; i <= now ; ++i)
        if (!in[i])
            ++ans;
    for(i = 1 ; i <= now ; ++i)
        if (ans > 1 && size_scc[i] == 1 && in[i] == 0)
        {
            --ans;
            break;
        }
    printf("%.6lf" , 1 - double(ans) / n);
    return 0;
}
comments powered by Disqus