1. 题目

传送门= ̄ω ̄=

或者也可以去 Luogu 看

2. 题解

设 $f[x]$表示从 $1$号点一直游走,游走到点 $x$都一直没有爆炸的概率。

$f[x]=(1 – \frac P Q) \sum {\frac {f[v]} {degree[v]}} + [u == 1]$

其中 $degree$表示一个点的度数,$[u == 1]$表示 $u$是否是 $1$号点,如果是则值为 $1$,否则为 $0$。

特判是否等于 $1$是因为起点是 $1$,因此其实直接说概率是不太严谨的,应该算一种期望吧。

然后高斯消元就行啦。

代码:

#include <bits/stdc++.h>

#define NS (305)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, p, q;

vector<int> g[NS];

double frc, d[NS][NS];

void Gs()
{
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = i + 1; j <= n; j += 1)
            if (d[i][i] < d[j][i]) swap(d[i], d[j]);
        for (int j = n + 1; j >= i; j -= 1)
            d[i][j] /= d[i][i];
        for (int j = i + 1; j <= n; j += 1)
            for (int k = n + 1; k >= i; k -= 1)
                d[j][k] -= d[j][i] * d[i][k];
    }
    for (int i = n; i >= 1; i -= 1)
        for (int j = 1; j < i; j += 1)
            d[j][n + 1] -= d[i][n + 1] * d[j][i];
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(p), IN(q), frc = (double)p / q;
    for (int i = 1, a, b; i <= m; i += 1)
        IN(a), IN(b), g[a].push_back(b), g[b].push_back(a);
    for (int i = 1; i <= n; i += 1)
    {
        d[i][i] = 1;
        for (int j = 0; j < g[i].size(); j += 1)
            d[i][g[i][j]] = (frc - 1) / g[g[i][j]].size();
        if (i == 1) d[i][n + 1] = 1;
    }
    Gs();
    for (int i = 1; i <= n; i += 1)
        printf("%.9lf\n", d[i][n + 1] * frc);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注