相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3534
矩阵树定理基础:http://oi.cyo.ng/?p=717
解题报告
说明:以下使用变量名,均同上面的矩阵树定理基础
这个题目直接看矩阵树定理肯定是没有头绪的。
但如果我们看矩阵树定理推导过程中的这个式子:\(\partial = {\sum\limits_{G’isG’sSubgraph} {\det (M(G’))} ^2}\)
不难发现我们可以这样算贡献:\(\partial = {\sum\limits_{G’isG’sSubgraph} {\det (M(G’))} ^2} \cdot P\)
其中p为,在生成树中的点的出现概率和不在生成树中的点的不出现的概率
于是现在的问题就是如何把概率给搞进去。不难发现如果我们把每条边的概率乘到M(G’)中,刚好可以满足树边那部分的概率,但非树边那部分还满足不了
于是再来考虑非树边,凑一凑发现:我们把p/(1-p)乘进去,全局再乘以(1-p)就可以满足条件了
所以L=M(G)*M(G)^T*p/(1-p)
所以直接把矩阵树定理的邻接矩阵的0/1变成概率就可以了
或者,更直接的理解:矩阵树定理里面的邻接矩阵可以推广到连边的个数,那应该可以推广到实数域,这样的话就可以对应概率了?
Code
1A辣,撒花~ ★,°:.☆( ̄▽ ̄)/$:.°★ 。
#include<iostream> #include<cstdio> #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int MAXN = 51; const double EPS = 1e-8; int n; double G[MAXN][MAXN],rev=1; inline double Gauss(){ double ret = 1; for (int j=1,w=j;j<=n;w=++j) { for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > abs(G[j][w])) w = k; if (w != j) {for (int i=1;i<=n;i++) swap(G[i][j],G[i][w]); ret *= -1;} for (int k=j+1;k<=n;k++) if (abs(G[j][k]) > EPS) { double t = G[j][k] / G[j][j]; for (int i=1;i<=n;i++) G[i][k] -= G[i][j]*t; } ret *= G[j][j]; } return ret; } int main(){ scanf("%d",&n); for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) scanf("%lf",&G[i][j]), rev *= i<j?1:1-G[i][j]; for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) G[i][j] = G[i][j]/(1-G[i][j])*-1; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i != j) G[i][i] -= G[j][i]; n--; printf("%.10lf\n",Gauss()*rev); return 0; }