#P3534. [Sdoi2014]重建

    ID: 2744 传统题 1000ms 512MiB 尝试: 1756 已通过: 587 难度: 7 上传者: 标签>难度分类提高+/省选-组合数学Matrix-Tree 定理数据结构普通并查集图论缩点线性代数与代数行列式高斯消元主元选择CF2300

[Sdoi2014]重建

[SDOI2014] 重建

题目描述

T 国的 NN 座城市由若干条双向道路连接,每对城市之间至多有一条道路。一次洪水导致一些道路无法通行。政府希望根据每条道路在洪水后仍可通行的概率,估计道路网络的状况。

给定各条道路仍可通行的概率。各条道路能否通行相互独立。求仍可通行的道路恰有 N−1N-1 条,并且这些道路连接所有城市的概率。

输入格式

第一行一个整数 NN。接下来 NN 行,每行 NN 个实数。矩阵第 ii 行第 jj 列的数 Gi,jG_{i,j} 表示城市 ii 与城市 jj 之间有可通行道路的概率。

保证 0≤Gi,j≤10\le G_{i,j}\le1、Gi,j=Gj,iG_{i,j}=G_{j,i}、Gi,i=0G_{i,i}=0,且 Gi,jG_{i,j} 最多有两位小数。

输出格式

输出一个实数。标准答案非零时,与标准答案的相对误差不得超过 10−410^{-4}。标准答案为零时,输出 00。

样例 #1

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0
0.375

样例 #2

5
0.00 0.95 0.96 0.95 0.00
0.95 0.00 0.95 0.95 0.96
0.96 0.95 0.00 0.85 0.02
0.95 0.95 0.85 0.00 0.85
0.00 0.96 0.02 0.85 0.00
0.0006095519875

数据范围

若答案非零,则答案不小于 10−410^{-4}。原赛各测试点的条件如下。

测试点 NN 其他约定
1 1≤N≤101\le N\le10 Gi,jG_{i,j} 为整数
2–3 非零概率的无向边不超过 2020 条
4–5 1≤N≤121\le N\le12 无
6–7 1≤N≤161\le N\le16
8–9 1≤N≤501\le N\le50 没有概率为 11 的边
10 无