P5814 [CTSC2001] Ultimate Intelligence Network.

Before the final Normandy landing battle began, the Allied and German intelligence agencies fought an unprecedented intelligence war over the final landing location. In this intelligence war, the Allied tactic was to use double agents hidden inside the enemy to release fake landing information to the heads of the German intelligence agencies. Those agents who had already infiltrated behind enemy lines were all elites of the Allied intelligence department, loyal and reliable. However, how to choose suitable people, and the best way to transmit messages, so that the fake information could be delivered to the German commanders as quickly, safely, and accurately as possible, became the biggest problem troubling the Allied intelligence minister. He needs your help. The minister provides the following operational data: There are a total of $N$ of our best spies behind enemy lines, numbered $1,2,\cdots,N$. Within the given operation time, any two people can make at most one point-to-point two-person contact. You will be given a table. The table provides the security level of a contact between any two spies $i$ and $j$, represented by a real number $S_{i,j}$ in $[0,1]$; and the maximum number of messages they can exchange in this contact, represented by a positive integer $M_{i,j}$ (if it is not mentioned in the table, then spies $i$ and $j$ do not contact directly). The channel for sending fake messages from the Allied headquarters to each spy is also not absolutely safe. We use a real number $AS_j$ in $[0,1]$ to represent the security level of contact between the headquarters and spy $j$, and $AM_j$ to represent the maximum number of messages that can be transmitted when the headquarters contacts spy $j$. For spies that do not contact the headquarters directly, $AM_j = 0$ (and the given $AS_j$ is meaningless). Of course, the process of delivering a fake message from a spy to the German intelligence officer’s desk is absolutely safe; that is, a spy either does not contact the German intelligence department directly, or the security level of that contact is $1$ (completely reliable). Now the intelligence department plans to “leak” $K$ fake messages to the Germans. The messages are first sent by the headquarters in one batch to some of the $N$ spies, then spread through their intelligence network, and finally delivered to the Germans by some of these $N$ spies. For a single message, the transmission is considered safe only if it passes safely through all intermediate steps and reaches the German intelligence department. Therefore, by the multiplication rule, its security level $P$ is the product of the security levels of every transmission of that message, from the headquarters through multiple transfers until it reaches the Germans. For the whole plan, it is successful only when all $K$ messages pass safely through the network and reach the Germans, with none raising suspicion. So the reliability of the plan is the product of the security levels of all messages. Obviously, the reliability depends on how these messages are transmitted in the network. You need a scheme that decides from whom to whom each message should be passed, so that the final reliability is maximized. You can use a computer to find the most reliable message transmission plan.

The input contains the Allied operational data table. The first line contains two integers $N$ and $K$, which are the total number of spies and the total number of messages in the plan. The second line contains $2N$ numbers. The first $N$ numbers are real numbers $AS_1,AS_2,\cdots,AS_N$ (in the range $[0,1]$). The next $N$ numbers are integers $AM_1,AM_2,\cdots,AM_N$. The third line contains $N$ integers. The $i$-th integer ($i = 1,2,\cdots,N$) is $0$ if spy $i$ does not contact the German intelligence department, and $1$ if spy $i$ does. Starting from the fourth line, each line contains $4$ numbers in order: the positive integers $i$ and $j$ representing spy IDs, the security parameter $S_{i,j}$ of the contact between spies $i$ and $j$ (a real number in $[0,1]$), and the maximum number of messages $M_{i,j}$ that can be transmitted between $i$ and $j$ (in each line, $i$ is less than $j$). The last line is `-1 -1`, which indicates the end of input.

Output only one line. This line contains a real number $P$, which is the reliability $P$ of the whole plan, **rounded to $5$ significant digits**. If the intelligence network cannot transmit $K$ messages to the Germans at all, then the plan reliability is $0$. (You may assume that if a plan exists, then its reliability is greater than $10^{-12}$.)

$1 \le N,K \le 300$. Translated by ChatGPT 5