• [1622] 连通图

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 首先我们了解无向图中的两个概念:

    (1)完全图:n 个点的图中任意两个点之间都有一条边相连,所以有 n*(n-1)/2 条边。(如下图)


    (2)连通图:图中任意两个点之间都有路径,所以至少得有 (n-1) 条边。(如下图)


    现在给出一个 n 个点的完全图,要从其中选择 k 条不同的边,问这 n 个点与选择的边能构成连通图的概率?

  • 输入
  • 多组输入数据。
    每组数据一行,有两个数 n 和 k。
    数据范围:1 <= n <= 4,0 <= k <= n*(n-1)/2 。
  • 输出
  • 对于每一组数据输出一行,代表概率,四舍五入到小数点后2位。(即:用 %.2f 输出)
  • 样例输入
  • 1 0
    2 0
  • 样例输出
  • 1.00
    0.00
  • 提示
  • 来源
  • 2015苏州大学ACM-ICPC集训队选拔赛(1)
  • 操作

显示春菜