2891. 匹配难题
#2891. 匹配难题
题目描述
给定一个二分图a,b.每条a->b的边都有一个存在的概率。求期望最大匹配数。
输入格式
第一行两个整数a,b
接下来一个a*b的矩阵表示i->j这条边存在的概率。
输出格式
一个实数表示期望最大匹配数。保留2位小数（注意C++以及PASCAL对于四舍五入的问题，比如PASCAL对于2.5四舍五入会输出2，建议输出时加一个极小量）
样例
样例输入
3 3
0.38064 0.30000 0.29486
0.41715 0.90000 0.67837
0.53316 1.00000 1.00000
【输出样例】
2.575940
【输入样例】
2 2
0.40000 1.00000
0.10000 1.00000
样例输出
1.46
【数据规模和约定】
10% a*b<=16
10% a = 1,b <= 100
10% a = 2,b <= 100
10% a = 3,b <= 100
20% a = 4,b <= 100
20% a = 5,b <= 100
20% a=6,b<=100