UOJ Logo Sharp Sword 剑锋 OI

SSOI

#31. 锦标赛

统计

【问题描述】

CZ 机房最近决定举行一场锦标赛。锦标赛共有 N 个人参加,共进行 N-1 轮。
第一轮随机挑选两名选手进行决斗,胜者进入下一轮的比赛,第二轮到第 N-1 轮再每轮随机挑选 1 名选手与上一轮胜利的选手决斗,最后只剩一轮选手。第 i 名选手与第 j 名选手决斗,第 i 名选手胜利的概率是 a[i][j].
作为一号选手的 OIer 想知道如何安排每轮出场的选手可以使得他获胜的概率最大,并求出这个最大概率。

【输入格式】

第一行两个整数n和m。
接下来m行每行两个整数表示一条有向边。保证无重边无自环。

【输出格式】

一个小数,表示最大概率。与答案误差不超过 10^(-5) 即算正确。

【输入样例1】

3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0

【输出样例1】

0.6800000

【样例解释】

第一轮 2 与 3 决斗,胜者与 1 决斗
如果 2 获胜,那么最后 1 获胜的概率为 a[2][3]*a[1][2]=0.2
如果 3 获胜,那么最后 1 获胜的概率为 a[3][2]*a[1][3]=0.48
所以总概率为 0.68

【时空限制】

1S
256MB
对于 30%的数据,N<=10
对于 60%的数据,N<=15
对于 100%的数据,N<=18