中文
日本語
English
| P2879【SDOI2014 R1D2】重建 | |
|
问题描述
此题需SPJ，请提交到BZOJ 3534
http://www.lydsy.com/JudgeOnline/problem.php?id=3534
T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。
在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。
幸运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。
输入格式
输入的第一行包含整数 。
接下来N行，每行N个实数，第i+1行j列的数G[i][j]表示城市i与j之间仍有道路联通的概率。
输入保证G[i][j]=G[j][i]，且G[i][i]=0；G[i][j]至多包含两位小数。
输出格式
/*
输出一个任意位数的实数表示答案。
你的答案与标准答案相对误差不超过10-4即视为正确。
*/
保留6位小数。
样例输入
样例输入1：
3
0 0.5 0.5
0.5 0 0.5
0.5 0.5 0
样例输入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
样例输出
样例输出1：
0.375000
样例输出2：
0.000610
提示
数据范围：
测试点1：1<=N<=10，G[i][j]为整数
测试点2-3：1<=N<=10，概率非零的边数不超过20
测试点4-5：1<=N<=12
测试点6-7：1<=N<=16
测试点8-9：1<=N<=50，不存在概率为1的边
测试点10：1<=N<=50
数据保证答案非零时，答案不小于10-4。