【BZOJ】【P3534】【Sdoi2014】【重建】【题解】【矩阵树定理】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3534
dt学了矩阵树定理
邻接矩阵中的的权可以不是1,而是其他权值,比如概率
这样计算出来的就是所有生成树的概率和,即
【【BZOJ】【P3534】【Sdoi2014】【重建】【题解】【矩阵树定理】】
文章图片
但是这样不对……
生成一颗生成树T的概率应该是
文章图片
接着就是神奇的转换
设G要求的矩阵,P是给出的矩阵
我们令
文章图片
文章图片
文章图片
对G计算n-1阶主子式,即有
文章图片
那么把它乘上tmp
答案就这么出来了!!!!
当P=1时处理需要一点小技巧,把它当做1-eps就可以了
Code:
#include
using namespace std;
int n;
const double eps=1e-10;
double A[55][55];
int dcmp(double x){return x<-eps?-1:x>eps;
}
double Gauss(){
double ans=1;
for(int i=1;
i>n;
double tmp=1;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=n;
j++){
cin>>A[i][j];
if(i==j)continue;
if(A[i][j]>1-eps)A[i][j]-=eps;
if(i 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长