#P3534. [Sdoi2014]重建
[Sdoi2014]重建
[SDOI2014] 重建
题目描述
T 国的 座城市由若干条双向道路连接,每对城市之间至多有一条道路。一次洪水导致一些道路无法通行。政府希望根据每条道路在洪水后仍可通行的概率,估计道路网络的状况。
给定各条道路仍可通行的概率。各条道路能否通行相互独立。求仍可通行的道路恰有 条,并且这些道路连接所有城市的概率。
输入格式
第一行一个整数 。接下来 行,每行 个实数。矩阵第 行第 列的数 表示城市 与城市 之间有可通行道路的概率。
保证 、、,且 最多有两位小数。
输出格式
输出一个实数。标准答案非零时,与标准答案的相对误差不得超过 。标准答案为零时,输出 。
样例 #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
数据范围
若答案非零,则答案不小于 。原赛各测试点的条件如下。
| 测试点 | 其他约定 | |
|---|---|---|
| 1 | 为整数 | |
| 2–3 | 非零概率的无向边不超过 条 | |
| 4–5 | 无 | |
| 6–7 | ||
| 8–9 | 没有概率为 的边 | |
| 10 | 无 |