Pku3156 Interconnect
时间限制：10s 空间限制：64MB
题目描述
给出无向图G(V, E). 每次操作任意加一条非自环的边(u, v), 每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000)
输入格式
第一行两个整数N,M 1<=N<=30 0<=M<=1000 接下来M行,每行两个整数X,Y表示两者之间已修好一条道路. 两点之间可以不止修了一条路,也有可能M条路已使N个点成为一个整体.
输出格式
输出一个小数,表示新修道路条数的期望值,保留六位小数.
样例输入
4 2 1 2 3 4
样例输出
1.500000
提示
没有写明提示
题目来源
没有写明来源