# 描述

A coding contest will be held in this university, in a huge playground. The whole playground would be divided into $N$ blocks, and there would be $M$ directed paths linking these blocks. The $i$-th path goes from the $u_i$-th block to the $v_i$-th block. Your task is to solve the lunch issue. According to the arrangement, there are $s_i$ competitors in the $i$-th block. Limited to the size of table, $b_i$ bags of lunch including breads, sausages and milk would be put in the $i$-th block. As a result, some competitors need to move to another block to access lunch. However, the playground is temporary, as a result there would be so many wires on the path.
For the $i$-th path, the wires have been stabilized at first and the first competitor who walker through it would not break the wires. Since then, however, when a person go through the $i$ - th path, there is a chance of $p_i$ to touch the wires and affect the whole networks. Moreover, to protect these wires, no more than $c_i$ competitors are allowed to walk through the $i$-th path.
Now you need to find a way for all competitors to get their lunch, and minimize the possibility of network crashing.

## Input

The first line of input contains an integer $t$ which is the number of test cases. Then $t$ test cases follow.
For each test case, the first line consists of two integers $N$ $(N ≤ 100)$ and $M$ $(M ≤ 5000)$. Each of the next $N$ lines contains two integers $s_i$ and $b_i$ $(s_i , b_i ≤ 200)$.
Each of the next $M$ lines contains three integers $u_i$ , $v_i$ and $c_i$$(c_i ≤ 100) and a float-point number p_i$$(0 < p_i < 1)$.
It is guaranteed that there is at least one way to let every competitor has lunch.

## Output

For each turn of each case, output the minimum possibility that the networks would break down. Round it to $2$ digits.

## 思路

• 看到这题开始就觉得是个网络流，而且应该是费用流。但是平时我们的费用流的费用都是单位流量的费用，而这题涉及到概率，有些不同。
• 先说建图：
• 判断每个点，如果这个点的人比食物多，就从源点到该点连一条边，否则从该点向汇点连一条边，容量为两者的差值，不发生危险的概率（费用）为$1$。
• 由于每条边第一次走是不会发生危险的，所以需要特殊化处理，先建一条容量为$1$，费用为$1$的边，然后再建容量为$c-1$，费用为$1-p$的边。
• 这样我们就要在这张图上最大化这个概率。（即求最大费用最大流）所以上述费用只要都取相反数，再跑最小费用最大流即可。
• 在跑费用流的时候，由于原本的费用流中的费用是单位流量的费用，即$cost=\sum {p_i \times d_i}$，而在这题中，$cost=\prod {p_i ^ {d_i}}$。所以我们需要修改一下费用流中费用的计算。
• 当然没有这么麻烦。我们可以两边取对数，即$\log cost = \sum {d_i \times \log p_i}$，这样就可以跑一个正常的费用流了，最后答案就是$1-e^{-cost}$。当然由于要计算的是最大费用，所以我们一样要取负对数！
• 由于费用是double类型，所以在做最短路增广的时候要注意一下精度问题。

0%