【网络流练习】defuze

2015年1月4日1,5470

连锁炸弹是恐怖分子最近开始使用的一种威力巨大的爆炸物。其复杂的结构使拆除它的难度大大增加了。

一个连锁炸弹由m个引爆装置和n枚炸弹组成。每个引爆装置中有n条信号线分别与这n枚炸弹相连(1号线连接炸弹1,2号线连接炸弹2,……)。与一枚炸弹相连的m条信号线中只有一条是“安全线”——剪断后可以拆除炸弹,而剪断其它信号线则引爆炸弹。

专业的技术人员将给出一个m×n的表格。其中第i行第j列显示了引爆装置i与炸弹j连接的信号线是“安全线”的可能性Pij(Pij∈(0,1)),并且已知每个引爆装置上的“安全线”数目不超过k。技术人员的分析结果是绝对值得信任的。

政府的安全部门常常雇佣一些程序员去设计解决突发情况的程序。其中一项任务正是提高排除连锁炸弹的成功率。成功的拆除一个连锁炸弹,必须切断与炸弹相连所有n条“安全线”。现在,请设计一个程序,求出应剪断哪n条信号线,才能使拆除所有炸弹的可能性 ∏ Pij(即所有剪断的信号线pij的乘积)最大。

输入文件

输入的第一行为3个整数m,n,k(用空格分隔开)。(m≤50,k≤n≤50)

接下来的m行,每行有n个实数(用空格分隔开)。这就是技术人员提供的表格,其内容已经在问题中详细说明了(pij为 (0,1) 的实数 )。

输出文件

仅一个数据,最大成功拆除的可能性(保留小数点后4位)。

输入样例

4 5 2

0.95 0.20 0.57 0.48 0.50

0.56 0.88 0.42 0.80 0.90

0.70 0.65 0.42 0.60 0.87

0.91 0.80 0.72 0.44 0.20

输出样例

0.4189

样例说明:

对应的拆除方案是:切断引爆装置1上的1号线;切断引爆装置2上的2,4号线;切断引爆装置3上的5号线;切断引爆装置4上的3号线。)

题解

乘法转对数加法后,作二分图带权最大匹配TAT

注意精度问题