锐客网

  1. 首页 > it技术 > >

BZOJ|BZOJ3534: [Sdoi2014]重建【变元矩阵树定理】

3534: [Sdoi2014]重建 变元矩阵树定理 邻接矩阵中是可以带权的， w i j wij wij表示 i , j i,j i,j的边权， e i ei ei表示边。
定义G ( i , j ) = G ( j , i ) = w i j G(i,j)=G(j,i)=wij G(i,j)=G(j,i)=wij，令G ( i , i ) = ? ∑ j ≠ i G ( i , j ) G(i,i)=?∑_{j≠i}G(i,j) G(i,i)=?∑j??=i?G(i,j)
那么 n ? 1 n?1 n?1阶主子式的值为 ∑ T ? T r e e ∏ e ∈ T w e \large \sum_{T\subseteq Tree}\prod_{e\in T}w_e ∑T?Tree?∏e∈T?we?
考虑题目中的概率，我们知道最后答案是 ∑ T ? T r e e ∏ e ∈ T P e ∏ e ? T P e \large \sum_{T \subseteq Tree} \prod_{e\in T} P_e \prod_{e \notin T}P_e ∑T?Tree?∏e∈T?Pe?∏e∈/?T?Pe?
但是我们之间将边权设为 P ( i , j ) P(i,j) P(i,j)的话，最后答案就变成了 ∑ T ? T r e e ∏ e ∈ T P e \large \sum_{T\subseteq Tree}\prod_{e\in T}P_e ∑T?Tree?∏e∈T?Pe?
所以我们考虑变一下这个式子，令 w i , j w_{i,j} wi,j?为 P ( i , j ) 1 ? P ( i , j ) \large \frac{P(i,j)}{1-P(i,j)} 1?P(i,j)P(i,j)?
式子就变成了 ∑ T ? T r e e ∏ e ∈ T P e 1 ? P e \large \sum_{T\subseteq Tree}\prod_{e\in T}\frac{P_e}{1-P_e} ∑T?Tree?∏e∈T?1?Pe?Pe??
然后将式子都乘上一个 ∏ e ( 1 ? P e ) \prod_{e} (1-P_e) ∏e?(1?Pe?)
【BZOJ|BZOJ3534: [Sdoi2014]重建【变元矩阵树定理】】就会发现式子变成了这样 ∑ T ? T r e e ∏ e ∈ T P e ∏ e ? T P e \large \sum_{T \subseteq Tree} \prod_{e\in T} P_e \prod_{e \notin T}P_e ∑T?Tree?∏e∈T?Pe?∏e∈/?T?Pe?
不就是我们要求的吗。

#include #include #define EXP 1e-8 using namespace std; int n; double Tmp,f[55][55]; double _abs(double x){return x<0?-x:x; } double Gauss(){ double Mul=1.0; for(int i=1; i(1.0-EXP)) f[i][j]-=EXP; if(i

    推荐阅读


    上一篇：Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D. Restore Permutation(线段树)

    下一篇：LeetCode 字符串中的第一个唯一字符