#P2891. 匹配难题

    ID: 1998 传统题 1000ms 512MiB 尝试: 128 已通过: 21 难度: 9 上传者: 标签>CF2600省选/NOI-状压 DP概率 DP广度优先搜索哈希表全子集枚举预计算转移滚动数组

匹配难题

题目描述

有一张左部 nn 个点,右部 mm 个点的二分图,左部点 uu 到右部点 vv 之间的边 u→vu\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\% 的数据,1≤n×m≤161\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\% 的数据,1≤n≤61\leq n\leq 6,1≤m≤1001\leq m\leq 100。