F.A.Qs Home Discuss ProblemSet Status Ranklist 1 Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,鸣谢Claris主持!欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 3534. -- [Sdoi2014]重建

3534: [Sdoi2014]重建

Time Limit: 10 Sec  Memory Limit: 512 MBSec  Special Judge
Submit: 1277  Solved: 628
[Submit][Status][Discuss]

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

Sample Output

0.375

HINT

1 < N < =50


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

Source

Round 1 Day 2

[Submit][Status][Discuss]

HOME Back