bzoj3534: [Sdoi2014]重建

题目链接

bzoj3534: [Sdoi2014]重建

题解

答案为所有合法生成树的概率之和
一个合法的生成树出现概率为选取边的概率积乘未选取边不出现概率
那么答案就是
(prod_e (1-p_e)sum_T prod_{ein T} {p_e over (1-p_e) })
计算的过程就是一个matrix tree的计算过程，
换一下行列式的权值就是了

代码

#include<cmath> 
#include<cstdio> 
#include<algorithm> 
#define db double 
const int maxn = 57; 
const db eps = 1e-8; 
db a[maxn][maxn]; 

db det(int n) { 
    for(int r,i = 1;i <= n;++ i) { 
        r = i; 
        for(int j = i + 1; j <= n;++ j)if(fabs(a[r][i]) < fabs(a[j][i])) r = j; 
        if(i != r) for(int j = i;j <= n;++ j) std:: swap(a[i][j],a[r][j]); 
        if(fabs(a[i][i] < eps)) return 0.0; 
        for(int j = i + 1;j <= n;++ j) { 
            db t = a[j][i] / a[i][i]; 
            for(int k = i;k <= n;++ k) a[j][k] -= a[i][k] * t; 
        } 
    } 
    db ret = 1.0; 
    for(int i = 1;i <= n;++ i) ret = ret * a[i][i]; 
    return ret; 
} 
int main() { int n; 
    scanf("%d",&n); 	
    double tmp  = 1.0; 
    for(int i = 1;i <= n;++ i) for(int j = 1;j <= n;++ j) { 
        scanf("%lf",&a[i][j]); 
        if(i == j) continue; 
        if(a[i][j] > 1.0 - eps) a[i][j] -= eps; 
        if(i < j) tmp *= 1 - a[i][j]; 
        a[i][j] /= 1 - a[i][j]; 
    } 
    for(int i = 1;i <= n;++ i) for(int j = 1;j <= n;++ j) 
        if(i != j) a[i][i] += a[i][j],a[i][j] = - a[i][j]; 
    db ans = det(n - 1) * tmp; 
    printf("%.5lf
",ans); 
}