bzoj#P2891. 匹配难题
匹配难题
题目描述
有一张左部 个点,右部 个点的二分图,左部点 到右部点 之间的边 的存在概率为 ,求期望最大匹配数。
输入格式
第一行两个整数 。
接下来一个 的实数矩阵 表示边的存在概率。
输出格式
一个实数表示期望最大匹配数,保留两位小数。
3 3
0.38064 0.30000 0.29486
0.41715 0.90000 0.67837
0.53316 1.00000 1.00000
2.58
2 2
0.40000 1.00000
0.10000 1.00000
1.46
数据规模与约定
对于前 的数据,。
分别存在 的数据,;
分别存在 的数据,;
存在 的数据,;
对于后 的数据,,。