【题解】BZOJ 3534 [SDOI2014]重建

Problem

给定每条路完好的概率,求恰好有 $n-1$ 条路联通了 $n$ 个城市的概率

Thought

$$ \sum_{T}\prod_{e\in T}p_e\prod_{e\notin T}(1-p_e) $$

变形可得

$$ \sum_{e}(1-p_e)\sum_{T}\prod_{e\in T}\frac{p_e}{1-p_e} $$

后面部分直接矩阵树定理完事

注意当 $p_e=1$ 时令 $p_e=1-eps$ ,防止出现 $0$ 的情况

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

#define double long double

const double eps = 1e-8;
const int N = 60;

double a[N][N];

double gauss(int n) {
    double ret = 1;
    for(int i = 1; i < n; ++ i) {
        int now = i;
        for(int j = i + 1; j <= n; ++ j)
            if(fabs(a[now][i]) < fabs(a[j][i]))
                now = j;
        if(fabs(a[now][i]) < eps) return 0;
        if(now != i)
            for(int j = 1; j <= n; ++ j)
                swap(a[now][j], a[i][j]);
        for(int j = i + 1; j <= n; ++ j) {
            double t = a[j][i] / a[i][i];
            for(int k = i; k <= n; ++ k)
                a[j][k] -= a[i][k] * t;
        }
        ret *= a[i][i];
    }
    return fabs(ret);
}
int n;
int main() {
    n = read();
    double tmp = 1;
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            scanf("%Lf", &a[i][j]);
            if(a[i][j] == 1)
                a[i][j] -= eps;
            if(i < j) tmp *= (1 - a[i][j]);
            a[i][j] /= (1.0 - a[i][j]);
        }
    }
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            if(i == j) continue;
            a[i][i] -= a[i][j];
        }
    }
    printf("%.8Lf\n", gauss(n) * tmp);
    return 0;
}
Comments

添加新评论