4311: 「CTSC2001」终极情报网

在最后的诺曼底登陆战开始之前，盟军与德军的情报部门围绕着最终的登陆地点展开了一场规模空前的情报战。 这场情报战中，盟军的战术是利用那些潜伏在敌军内部的双重间谍，将假的登陆消息发布给敌军的情报机关的负责人。那些已经潜入敌后的间谍们都是盟军情报部的精英，忠实可靠；但是如何选择合适的人选，以及最佳的消息传递方法，才能保证假消息能够尽快而且安全准确地传递到德军指挥官们的耳朵里，成了困扰盟军情报部长的最大问题。他需要你的帮助。 以下是情报部长提供的作战资料： 在敌后一共潜伏着我方最优秀的N名间谍，分别用数字 $1, 2, …, N$ 编号。在给定的作战时间内，任意两人之间至多只进行一次点对点的双人联系。 我将给你一份表格，表格中将提供任意两位间谍i和j之间进行联系的安全程度，用一个 $[0, 1]$ 的实数 $S_{i,j}$ 表示；以及他们这次联系时，能够互相传递的消息的最大数目，用一个正整数表示 $M_{i,j}$ (如果在表格中没有被提及，那么间谍i和j之间不进行直接联系)。 假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安全，我们用 $[0, 1]$ 的实数 $AS_j$ 表示总部与间谍 $j$ 之间进行联系的安全程度， $AM_j$ 则表示总部和间谍j之间进行联系时传递的消息的最大数目。对于不和总部直接联系的间谍，他的 $AM_j=0$ (而表格中给出的他的ASj是没有意义的)。 当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的过程是绝对安全的，也即是说，间谍与敌军情报部门之间要么不进行直接联系，要么其联系的安全程度是 $1$ (即完全可靠)。 现在情报部打算把 $K$ 条假消息“透露”到德军那里。消息先由总部一次性发给 $N$ 名间谍中的一些人，再通过他们之间的情报网传播，最终由这 $N$ 名间谍中的某些将情报送到德军手中。 对于一条消息，只有安全的通过了所有的中转过程到达敌军情报部，这个传递消息的过程才算是安全的；因此根据乘法原理，它的安全程度P就是从总部出发，经多次传递直到到达德军那里，每一次传递该消息的安全程度的乘积。 而对于整个计划而言，只有当N条消息都安全的通过情报网到达德军手中，没有一条引起怀疑时，才算是成功的。所以计划的可靠程度是所有消息的安全程度的乘积。 显然，计划的可靠性取决于这些消息在情报网中的传递方法。 我需要一个方案，确定消息应该从哪些人手中传递到哪些人手中，使得最终计划的可靠性最大。 你可以利用计算机，来求得这个最可靠的消息传递方案。

输入包含了盟军的作战资料表格。 第一行包括两个整数 $N$ 和 $K$ ，分别是间谍的总人数和计划包含的消息总数。 第二行包括 $2N$ 个数，前 $N$ 个数是实数 $AS_1, AS_2,\dotsb, AS_N$ (范围在 $[0, 1]$ 以内)；后N个数是整数 $AM_1, AM_2,\dotsb, AM_N$ 。 第三行包含了 $N$ 个整数，其中第 $i(i = 1, 2, …, N)$ 个整数如果为 $0$ 表示间谍 $i$ 与德军情报部不进行联系，如果为 $1$ 则表示间谍与德军情报部进行联系。 第四行开始，每行包括 $4$ 个数，依次分别是：代表间谍编号的正整数 $i$ 和 $j$ ，间谍 $i$ 和 $j$ 联系的安全性参数 $S_{i,j}$ ( $[0,1]$ 范围内的实数)，以及 $i,j$ 之间传递的最大消息数 $M_{i,j}$ (每一行的 $i$ 均小于 $j$)。 最后的一行包含两个整数 $-1~ -1$ ，表示输入数据的结束。

输出只有一行。这一行中包含一个实数 $P$ ，给出的是整个计划的可靠程度 $P$ ，保留 $5$ 位有效数字(四舍五入)。 如果情报网根本不能将 $K$ 条消息传到德军手中，那么计划的可靠性为 $0$ 。 (你可以假定，如果计划存在，那么它的可靠性大于 $10^{-12}$)

6  13
0.9  0.7  0.8  0  0  0  2  6  8  0  0  0
0  0  0  1  0  1
1  4  0.5  2
2  3  0.9  5
2  5  0.8  2
2  6  0.8  7
3  5  0.8  2
5  6  0.8  4
-1  -1

0.00021184