【bzoj 3534】 [SDOI2014] 重建 - 基尔霍夫矩阵

题意： 　　给一个图，每条边有出现概率，求这个图恰好为一棵树的概率。 　 解法： 　　考虑Kirchhoff矩阵的意义：K[G]=D[G]−A[G]=B[G]B[G]T$K[G]=D[G]-A[G]=B[G]B[G]^{T}$，之所以能够进行生成树计数是对于其伴随矩阵在计数n−1$n-1$条边的集合时，当n−1$n-1$条边中存在环就会产生线性组合而导致行列式为零，否则恰好对角线上均为伴随矩阵中所赋的值，使得det(Bi,j)2$/det(B_{i,j})^2$就为1。 　　因此我们可以令邻接矩阵中存下边权，使得可以用Kirchhoff矩阵计数生成树中边权的乘积。 　　考虑到答案为∑T是一棵生成树∏u,v(p(u,v)∗[(u,v)∈T])((1−p(u,v))∗[u,v∉T])$/sum_{T是一棵生成树}/<a href="http://pr.VeVb.com/">PR</a>od_{u,v}(p(u,v)*[(u,v)/in T])((1-p(u,v))*[u,v/notin T])$，我们可以令边权为p(u,v)/(1−p(u,v))$p(u,v)/(1-p(u,v))$，求出行列式然后再乘回分母。 　　但是注意到p(u,v)==1$p(u,v)==1$时分母为0，此时我们理论上可以用一个足够小的ϵ$/epsilon$来表示0，考虑到double的表示法，取ϵ=2−20$/epsilon=2^{-20}$就足够了，这样可以避免过大/过小数运算所导致的精度误差，而原先的概率的精度（两位小数）也是可以接受的。 　　时间复杂度O(n3)$O(n^3)$，不知道为什么出题人出这么小，可能是怕数据都是0然后被水过去吧。