[概率期望][矩阵树][高斯消元]luogu P3317 重建 分析
https://www.luogu.org/problem/P3317
题目要求$sum_{T} (prod_{ein T} p_e prod_{e otin T}(1-p_e) )$
乍一看很像矩阵树，但是又不是
我们化一下柿子：
$sum_{T} (prod_{ein T} p_e frac{prod_{e}(1-p_e)}{prod_{ein T}(1-p_e)} )$
$prod_{e}(1-p_e)sum_{T} ( frac{prod_{ein T} p_e}{prod_{ein T}(1-p_e)} )$
套矩阵树模板就可以了
#include <iostream> #include <cstdio> using namespace std; typedef double db; const db eps=1e-8; const int N=60; int n; db g[N][N],k=1.0,ans=1.0; void Gauss(int n) { int mx;db t; for (int i=1;i<=n;i++) { mx=i; for (int j=i+1;j<=n;j++) if (g[mx][i]<g[j][i]) mx=j; if (mx!=i) swap(g[mx],g[i]); if (g[i][i]==0) { ans=0; return; } for (int j=i+1;j<=n;j++) { t=g[j][i]/g[i][i]; for (int k=i;k<=n;k++) g[j][k]-=g[i][k]*t; } ans*=g[i][i]; } if (ans<0) ans=-ans; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { scanf("%lf",&g[i][j]); if (g[i][j]==1) g[i][j]=1.0-eps; if (i<j) k*=1.0-g[i][j]; g[i][j]=g[i][j]/(1.0-g[i][j]); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (j!=i) g[i][i]+=g[i][j],g[i][j]=-g[i][j]; Gauss(n-1); printf("%.9lf",ans*k); }