TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2879
  • Problem
  • P2879【SDOI2014 R1D2】重建
    Limits : Time Limit : 10000 MS   Memory Limit : 565536 KB  SPJ
    Description

    此题需SPJ,请提交到BZOJ 3534
    http://www.lydsy.com/JudgeOnline/problem.php?id=3534
    T国有N个城市,用若干双向道路连接。一对城市之间至多存在一条道路。
    在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。
    幸运的是,此前T国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有N-1条,且能联通所有城市的概率。

    Input Format

    输入的第一行包含整数 。
    接下来N行,每行N个实数,第i+1行j列的数G[i][j]表示城市i与j之间仍有道路联通的概率。
    输入保证G[i][j]=G[j][i],且G[i][i]=0;G[i][j]至多包含两位小数。

    Output Format

    /*
    输出一个任意位数的实数表示答案。
    你的答案与标准答案相对误差不超过10-4即视为正确。
    */
    保留6位小数。

    Sample Input

    样例输入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

    Sample Output

    样例输出1:
    0.375000

    样例输出2:
    0.000610

    Hint

    数据范围:
    测试点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。


    Source  感谢nodgd放题