BZOJ3534:[SDOI2014]重建(矩阵树定理)
2024-08-26 13:55:10
Description
T国有N个城市,用若干双向道路连接。一对城市之间至多存在一条道路。
在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。
幸运的是,此前T国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有N-1条,且能联通所有城市的概率。
Input
输入的第一行包含整数N。
接下来N行,每行N个实数,第i+l行,列的数G[i][j]表示城市i与j之
间仍有道路联通的概率。
输入保证G[i][j]=G[j][i],且G[i][j]=0;G[i][j]至多包含两位小数。
Output
输出一个任意位数的实数表示答案。
你的答案与标准答案相对误差不超过10^(-4)即视为正确。
Sample Input
3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0
Sample Output
0.375
HINT
1 < N < =50
数据保证答案非零时,答案不小于10^-4
Solution
题目即让求:($T$是生成树,$e$是边)
$\sum_{T}\prod_{e\in T} p_e \prod_{e\notin T}(1-p_e)$
把第二个$\prod$变一下
$\sum_{T}\prod_{e\in T} p_e \frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)}$
也就是
$\prod_{e}(1-p_e)\sum_{T}\prod_{e\in T} \frac{p_e}{1-p_e}$。
其中行和矩阵$-$边权矩阵的行列式的值$=\sum_{T}\prod_{e\in T} w_e$,其中$w$是边权。
然后就可以高斯消元求解了。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N (59)
#define eps (1e-10)
using namespace std; int n;
double a[N][N],f[N][N],ans=; void Gauss()
{
int w=;
for (int i=; i<=n-; ++i)
{
int num=i;
for (int j=i+; j<=n-; ++j)
if (fabs(f[j][i])>fabs(f[num][i])) num=j;
if (num!=i) swap(f[num],f[i]), w=-w;
for (int j=i+; j<=n-; ++j)
{
double t=f[j][i]/f[i][i];
for (int k=i; k<=n-; ++k)
f[j][k]-=t*f[i][k];
}
}
for (int i=; i<=n-; ++i) ans*=f[i][i];
for (int i=; i<=n; ++i)
for (int j=i+; j<=n; ++j)
ans*=-a[i][j];
printf("%.10lf\n",ans*w);
} int main()
{
scanf("%d",&n);
for (int i=; i<=n; ++i)
for (int j=; j<=n; ++j)
{
scanf("%lf",&a[i][j]);
if (a[i][j]==) a[i][j]-=eps;
if (i==j) continue;
f[i][j]=-a[i][j]/(-a[i][j]);
f[i][i]-=f[i][j];
}
Gauss();
}
最新文章
- Coder-Strike 2014 - Round 1 D. Giving Awards
- java枚举使用详解
- Android课程---Android Studio安装及使用
- @Factory和@DataProvider的区别
- epub-2格式电子书剖析之一:文档构成
- Android进程通信之一:两种序列化方式
- BigDecimal 类型转换、运算、比较
- 教你写Makefile(很全,含有工作经验的)
- Mybatis中tinyint(1)数据自动转化为boolean处理
- nohup top -p 22452 -b >;>;jiu.log &;
- Kilani and the Game CodeForces - 1105D (bfs)
- 使用MATPLOTLIB 制图(散点图,热力图)
- glassfish3新建domain
- ant的hello world很好的官方文档[z]
- stl源码分析之list
- [转] Mac系统终端命令行不执行命令 总出现command not found解决方法
- 并发-ThreadLocal源码分析
- POJ2406 Power Strings(KMP)
- DDD学习笔录——简介DDD的战术模式、问题空间和解空间
- 3.4-3.6 依据业务需求分析HBase的表设计