$$\Large\texttt{My Blog}$$


Description

题目链接:Luogu 2973

有一个 $n$ 个点 $m$ 条边的无向图,节点 $1$ 有一个炸弹,在每个单位时间内,这个炸弹有 $\frac{P}{Q}$ 的概率在这个节点炸掉,有 $1-\frac{P}{Q}$ 的概率等概率选择一条与当前节点相连的边到其他的节点上。求炸弹在每个节点上爆炸的概率。

数据范围: $2\le n\le 300$ , $1\le m\le 44850$ , $1\le P,Q\le 10^6$


Solution

很显然,如果我们设第 $i$ 个点的期望经过次数为 $f_i$ ,那么第 $i$ 个点的爆炸概率为 $f_i\times\frac{P}{Q}$ 。那么我们只需要求出这个 $f_i$ 即可。

对于 $f_i$ 我们有如下关系式: $$f_u=\begin{cases}1& i=1 \\\sum_{(u,v)\in E} (1-\frac{P}{Q})\times \frac{f_v}{deg_v} & \text{otherwise}\end{cases}$$ 其中 $deg_i$ 表示第 $i$ 个点的度数。这个式子的含义为:当到达 $u$ 时,当且仅当在 $v$ 的位置不爆炸并且有 $\frac{1}{deg_v}$ 的概率从 $v$ 走到 $u$ 的位置。

我们直接高斯求和一波就好了。

时间复杂度: $O(n^3)$


Code

#include <cstdio>
#include <cmath>
#include <algorithm>

const int N=305;
int n,m,p,q,e[N][N],deg[N];
double a[N][N],b[N],x[N];

void Gauss(int n) {
    for(int i=1;i<=n;++i) {
        int p=i;
        for(int k=i+1;k<=n;++k) if(fabs(a[k][i])>fabs(a[p][i])) p=k;
        if(i!=p) std::swap(a[i],a[p]),std::swap(b[i],b[p]);
        for(int k=i+1;k<=n;++k) {
            double d=a[k][i]/a[i][i];
            b[k]-=d*b[i];
            for(int j=i;j<=n;++j) a[k][j]-=d*a[i][j];
        }
    }
    for(int i=n;i>=1;--i) {
        for(int j=i+1;j<=n;++j) b[i]-=x[j]*a[i][j];
        x[i]=b[i]/a[i][i];
    }
}
int main() {
    scanf("%d%d%d%d",&n,&m,&p,&q);
    double P=1.0*p/q;
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u][v]=e[v][u]=1,++deg[u],++deg[v];
    }
    for(int i=1;i<=n;++i) {
        a[i][i]=1.0;
        for(int j=1;j<=n;++j) {
            if(e[i][j]) a[i][j]-=(1.0-P)/deg[j];
        }
    }
    b[1]=1.0;
    Gauss(n);
    for(int i=1;i<=n;++i) printf("%.9lf\n",x[i]*P);
    return 0;
}