[AdditionalFile6985.zip](file://AdditionalFile6985.zip?type=additional_file)

#6985. 「ICPC World Finals 2025」管道新娘

标签: 传统 | 时间限制: 12000 ms | 内存限制: 2048 MiB |

题目描述

故事还在继续！几年来，你的小镇一直被一种叫做 Flubber 的物质所「恩赐」——这种人造化学物质虽然可爱，但略带易燃、有毒、酸性、有感知力且爱搞恶作剧的特性。人们仍在继续寻找这种物质的更多（或者说，任何）用途。但与此同时，Flubber 工厂仍在全速生产它。关闭工厂的努力已经失败，部分原因是谁也不知道究竟是谁在经营这家工厂。

你的任务是将源源不断流出的 Flubber 存储在不同的 Flubber 水库中，以备将来使用（或者，至少是为了让它不再烦扰大家——字面意义上的「不再沾到每个人的头发上」）。为了完成这项任务，你拥有一个复杂的 Flubber 管道网络，连接着各种 Flubber 站点和水库。

每个 Flubber 站点都有一条或多条通向外部的 Flubber 管道，并设有各种可以升降的闸门，以便将流入的 Flubber 以任何期望的比例排入输出的 Flubber 管道。例如，你可以将所有的 Flubber 送入一条管道，或者按 $25-75$ 的比例分配给两条管道等。

相比之下，一条 Flubber 管道会流向一个或多个较低的站点或水库，但 Flubber 以你无法控制的固定比例排入它们。也可能有一部分 Flubber 流失到环境中，但那是你继任者的问题，而不是你的。

你希望尽快填满所有水库。也就是说，在所有可能的站点排水配置中，你希望最大化流入任何一个水库的 Flubber 流量的最小值。

图 C.1 展示了两个样例输入。站点和水库用编号的节点表示，站点为绿色，水库为蓝色。管道用白色节点表示。例如，在第一个样例输入（左图）中，Flubber 可以从站点 $1$ 以任意比例输送到其下游的两条管道中，但每条管道将根据其出边上打印的百分比来分配其流入量。

输入的第一行包含三个整数 $s, r, d$，其中 $s$ $(1 \leq s \leq 10000)$ 是站点的数量，$r$ $(1 \leq r \leq 3)$ 是水库的数量，$d$ $(s \leq d \leq 20000)$ 是管道的数量。站点编号从 $1$ 到 $s$，水库编号从 $s+1$ 到 $s+r$。编号是按海拔高度降序排列的。工厂的 Flubber 最初流入站点 $1$。

接下来的 $d$ 行中，每一行都以两个整数 $i$ 和 $n$ 开始，其中 $i$ $(1 \leq i \leq s)$ 是可以排入此管道的站点，$n$ $(1 \leq n \leq 10)$ 是此管道的输出数量。该行的其余部分包含 $n$ 对整数 $o$ 和 $p$，其中 $o$ $(i < o \leq s+r)$ 是该管道排向的站点或水库，$p$ $(1 \leq p \leq 100)$ 是进入该管道的 Flubber 将排向 $o$ 的百分比。对于给定的管道，其 $o$ 值是唯一的。每个站点至少有一条可以排入的管道。给定管道的输出百分比总和最多为 $100$。

输出格式

输出一个百分比 $f$，这是在某种站点排水配置下，所有水库都能接收到至少 $f\%$ 的工厂生产的 Flubber 的最高可能百分比。你的答案的绝对误差不能超过 $10^{-6}$。

样例 1

输入

2 3 3
1 2 3 80 4 10
1 2 2 40 4 30
2 1 5 100

输出

24.0

样例 2

输入

1 2 3
1 1 2 50
1 1 3 50
1 2 2 40 3 60

输出

42.8571428571