Luogu P2973 [USACO10HOL]Driving Out the Piggies G

发现答案其实与这个点炸弹经过的次数有关，因为只要知道了这个点炸弹经过次数 \(w\)，这个点答案就能算出：\(w\times \frac{p}{q}\)

就想到设 \(f_u\) 为 \(u\) 点炸弹经过次数
\(u\) 点经过次数便可以由有连边的 \(v\) 点推来，要满足 \(v\) 点此时炸弹没爆炸且 \(deg_v\) 条边中选了 \(u\) 这一条边，要注意若为 \(1\) 号点起始经过了 \(1\) 次
\(f_u = \begin{cases}(1 - \frac{p}{q}) \sum \frac{f_v}{deg_v}& (u \not = 1)\\ 1 + (1 - \frac{p}{q}) \sum \frac{f_v}{deg_v} & (u = 1)\end{cases}\)

然后会发现这个东西有环，用高斯消元处理得到对应的 \(f_u\) 算出答案即可

时间复杂度 \(O(n^3)\)

#include<bits/stdc++.h>
using namespace std;
#define ldouble long double
const int N = 3e2 + 5;
vector<int> to[N];
int deg[N];
void add(int u, int v) {
    to[u].push_back(v); deg[v]++;
    return ;
}
ldouble g[N][N];
ldouble ans[N];
int main() {
    int n, m, p, q;
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    ldouble s = 1.0 * p / q;
    g[1][n + 1] = 1.0;
    for (int i = 1; i <= n; i++) {
        g[i][i] = 1.0;
        for (int j : to[i]) {
            g[i][j] = -(1.0 - s) / deg[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        int h = i;
        for (int j = i + 1; j <= n; j++) {
            if (fabs(g[j][i]) > fabs(g[h][i])) {
                h = j;
            }
        }
        swap(g[i], g[h]);
        for (int j = n + 1; j >= i; j--) {
            g[i][j] /= g[i][i];
        }
        for (int j = i + 1; j <= n; j++) {
            for (int k = n + 1; k >= i; k--) {
                g[j][k] -= g[j][i] * g[i][k];
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        ans[i] = g[i][n + 1];
        for (int j = i - 1; j >= 1; j--) {
            g[j][n + 1] -= ans[i] * g[j][i];
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%.9Lf\n", ans[i] * s);
    }
    return 0;
}