bzoj#P2891. 匹配难题

匹配难题

题目描述

有一张左部 nn 个点,右部 mm 个点的二分图,左部点 uu 到右部点 vv 之间的边 uvu\to v 的存在概率为 pu,vp_{u,v},求期望最大匹配数。

输入格式

第一行两个整数 n,mn,m

接下来一个 n×mn\times m 的实数矩阵 pp 表示边的存在概率。

输出格式

一个实数表示期望最大匹配数,保留两位小数。

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

数据规模与约定

对于前 10%10\% 的数据,1n×m161\leq n\times m\leq 16

分别存在 10%10\% 的数据,n=1,2,3n=1,2,3

分别存在 20%20\% 的数据,n=4,5n=4,5

存在 20%20\% 的数据,n=6n=6

对于后 90%90\% 的数据,1n61\leq n\leq 61m1001\leq m\leq 100