「Luogu 2973」Dotp

发表于 | | 阅读次数:
字数统计: 551 字

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​$ 我们有如下关系式：

其中 $deg_i​$ 表示第 $i​$ 个点的度数。这个式子的含义为：当到达 $u​$ 时，当且仅当在 $v​$ 的位置不爆炸并且有 $\frac{1}{deg_v}​$ 的概率从 $v​$ 走到 $u​$ 的位置。

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

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

Code

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
 
#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;
}
0%