题解 P2973 【[USACO10HOL]Driving Out the Piggies G】

jun头吉吉 · 2020-07-28 13:54:29 · 题解

P2973 [USACO10HOL]Driving Out the Piggies G

题意

给出一张n个点，m条边的无向图，节点1有一个炸弹，在每个单位时间内，有\dfrac {p}{ q}的概率在这个节点炸掉，有1-\dfrac{p}q的概率随机选择一条出去的路到其他的节点上，去每个节点的概率相等。问最终炸弹在每个节点上爆炸的概率。

题解

考场上做到这道题，一脸蒙蔽

我们看一下下面这个与本题无关例子：

小明、小红、小芳在通过手心手背的游戏来决定哪两个人先出场，若有两个人同时出手心或手背那就让那两个人出场，否则重复游戏。问：小明与小红先出场的概率是多少？

很容易地我们知道，第一局有\dfrac 1 4的可能是小明与小红先出场，也有可能是\dfrac14的概率重开一局，再下一局也是如此。因此我们可以设小明与小红先出场的概率为x，显然：

x=\frac14+\frac14x

那么这两题有什么相同点呢？由于两题都没有限制次数，因此我们无法通过有限次便利得到答案。那我们就根据上一题的方法：设未知数

我们假设到第i个点的概率为x_i，入度为d_i，那么考虑其是炸弹可以从哪里来：

• 如果这个点是1号点，那么其概率是一开始的炸弹爆炸或者是与它相连的点的如果不爆炸就会炸弹就有可能转一到这个点，即：

  x_1=\dfrac pq+\sum_{(1,j)\in E}x_j \times (1-\dfrac p q)\times\dfrac 1 d_j

• 如果这个点是其他点，那就只能从相邻的点转移过来

  x_i=\sum_{(i,j)\in E}x_j \times (1-\dfrac p q)\times\dfrac 1 d_j

式中p、q、d均为常数，因此所有的柿子可以组成一个n元一次方程组然后就到了我们喜闻乐见的手解300元方程高斯消元的过程了

#include<bits/stdc++.h> 
#define maxn 310
#define eps (1e-6)
using namespace std;
int n,m,p,q,x,y;
int f[310][310];
int in[310];
double a[maxn][maxn];
void gauss_jordan(){
    for(int i=1;i<=n;++i){
        int r=i;
        for(int j=i+1;j<=n;++j)
            if(fabs(a[r][i])<fabs(a[j][i]))
                r=j;
        if(r!=i)
            for(int j=1;j<=n+1;++j)
            swap(a[i][j],a[r][j]);
            for(int j=1;j<=n;++j)if(j!=i){
                double tmp=a[j][i]/a[i][i];
                for(int k=i+1;k<=n+1;++k)
                    a[j][k]-=a[i][k]*tmp;
            }
    }
    for(int i=1;i<=n;++i)
        a[i][n+1]/=a[i][i];
}
int main(){
    //freopen("dotp.in","r",stdin);
    //freopen("dotp.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&p,&q);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        f[x][y]=f[y][x]=true;
        in[x]++;in[y]++;
    }
    a[1][n+1]=1.0*p/q;
    for(int i=1;i<=n;i++){
        a[i][i]=1;
        for(int j=1;j<=n;j++)
            if(f[i][j])
                a[i][j]=-(1-(double)p/q)/in[j];
    }
    gauss_jordan();
    for(int i=1;i<=n;i++)
        printf("%.9lf\n",a[i][n+1]);
    return 0;
}