题目地址：洛谷：【P2973】[USACO10HOL]赶小猪Driving Out the Piggi… – 洛谷、BZOJ：Problem 1778. — [Usaco2010 Hol]Dotp 驱逐猪猡

题目描述

一个无向图，节点1有一个炸弹，在每个单位时间内，有p/q的概率在这个节点炸掉，有1-p/q的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。

输入输出格式

输入格式：
* Line 1: Four space separated integers: N, M, P, and Q
* Lines 2..M+1: Line i+1 describes a road with two space separated integers: A_j and B_j

输出格式：
* Lines 1..N: On line i, print the probability that city i will be destroyed as a floating point number. An answer with an absolute error of at most 10^-6 will be accepted (note that you should output at least 6 decimal places for this to take effect).

输入输出样例

输入样例#1：

2 1 1 2 
1 2 

输出样例#1：

0.666666667 
0.333333333 

题解

我们考虑每次到达每个点爆炸是等可能的，因此在每个点爆炸的概率之比等于到达每个点的期望次数之比。而到达每个点的期望次数可以通过以下式子算出
\mathrm{E}(u) = \sum_{(u, v) \in E} \frac{\mathrm{E}(v) \times (1 - p / q)}{\mathrm{degree}[v]}
由于原图不一定是树，无法直接转移，我们考虑高斯消元的解法。对于除了1的节点，到达该点的期望次数等于右边这个求和，而对于节点1，由于一开始就在1位置，次数多1，方程等号右边就是1。
我们求出的是期望次数，和不为1，而概率和为1，需要加起来除一下才能得到答案。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cmath>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 305, EPS = 1e-10;

int n, m, u, v, p, q, gra[MAXN][MAXN], deg[MAXN];
double mat[MAXN][MAXN];

inline void gauss() {
    for(int i = 1; i <= n; i++) {
        int r = i;
        for(int j = i + 1; j <= n; j++) {
            if(std::fabs(mat[r][i]) < std::fabs(mat[j][i])) r = j;
        }
        if(r != i) {
            for(int j = 1; j <= n + 1; j++) {
                std::swap(mat[r][j], mat[i][j]);
            }
        }
        for(int j = 1; j <= n; j++) {
            if(j != i) {
                double t = mat[j][i] / mat[i][i];
                for(int k = i + 1; k <= n + 1; k++) {
                    mat[j][k] -= mat[i][k] * t;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        mat[i][n + 1] /= mat[i][i];
    }
}

int main() {
    n = readint(); m = readint(); p = readint(); q = readint();
    while(m--) {
        u = readint(); v = readint();
        gra[u][v] = gra[v][u] = 1;
        deg[u]++; deg[v]++;
    }
    for(int i = 1; i <= n; i++) {
        mat[i][i] = 1;
        for(int j = 1; j <= n; j++) {
            if(gra[i][j]) mat[j][i] = -(1 - double(p) / q) / deg[i];
        }
    }
    mat[1][n + 1] = 1;
    gauss();
    double sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += mat[i][n + 1];
    }
    for(int i = 1; i <= n; i++) {
        printf("%.9lf\n", mat[i][n + 1] / sum);
    }
    return 0;
}