#P3317. [SDOI2014] 重建

    ID: 5100 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2014山东Special Judge生成树期望

[SDOI2014] 重建

题目描述

T 国有 NN 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。

在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。

幸运的是,此前 T 国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有 N1N-1 条,且能联通所有城市的概率。

输入格式

输入的第一行包含整数 NN

接下来 NN 行,每行 NN 个实数,第 i+1i+1 行,列的数 Gi,jG_{i,j} 表示城市 iijj 之间仍有道路联通的概率。

输入保证 Gi,j=Gj,iG_{i,j}=G_{j,i},且 Gi,i=0G_{i,i}=0Gi,jG_{i, j} 至多包含两位小数。

输出格式

输出一个任意位数的实数表示答案。

你的答案与标准答案相对误差不超过 10410^{-4} 即视为正确。

3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0
0.375

提示

1<N501<N\leq 50

数据保证答案非零时,答案不小于 10410^{-4}