匹配难题

时间限制:10s      空间限制:128MB

题目描述

给定一个二分图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

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose