P12815 [NERC 2021] Budget Distribution

在资源有限且约束众多的情况下分配预算资金是一个难题。一个**预算计划**包含 $t$ 个主题；第 $i$ 个主题包含 $n_i$ 个项目。 对于每个主题，已知其**最优相对资金分配**。主题 $i$ 的最优相对分配是一个实数列表 $p_{i,j}$，其中 $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$。 设 $c_{i, j}$ 表示分配给主题 $i$ 的第 $j$ 个项目的资金金额；该主题的总资金为 $C_i = \sum\limits_{j=1}^{n_i}{c_{i,j}}$。主题 $i$ 的**非最优性**定义为 $\sum\limits_{j=1}^{n_i}\left|\frac{c_{i, j}}{C_i} - p_{i, j}\right|$。通俗地说，非最优性是所有项目中实际分配资金比例与最优比例的总差异。**总计划非最优性**是所有 $t$ 个主题的非最优性之和。你的任务是最小化总计划非最优性。 然而，目前尚不清楚具体可用的资金总额。主题 $i$ 的第 $j$ 个项目已经分配了 $\hat c_{i,j}$ 美元，且这些资金不可撤回。此外，还有 $q$ 种可能的额外未分配资金金额 $x_k$。对于每种情况，你需要计算在所有分配该额外资金的方式中，可能的最小总非最优性。分配给项目的资金金额不必是整数，任何实数均可，但所有额外资金必须全部分配到各个项目中（即在 $\hat c_{i,j}$ 的基础上增加）。 形式化地说，对于每种额外资金 $x_k$，你需要找到其分配方案 $d_{i,j}$，满足 $d_{i, j} \ge 0$ 且 $\sum\limits_{i=1}^{t}\sum\limits_{j=1}^{n_i} d_{i,j} = x_k$，使得最终预算分配 $c_{i,j} = \hat c_{i,j} + d_{i,j}$ 的总计划非最优性最小。

第一行包含两个整数 $t$（$1 \le t \le 5 \cdot 10^4$）和 $q$（$1 \le q \le 3 \cdot 10^5$）——预算中的主题数量和可能的额外资金金额数量。 接下来的 $t$ 行描述各个主题。每行以一个整数 $n_i$（$2 \le n_i \le 5$）开头，表示第 $i$ 个主题的项目数量；随后是 $n_i$ 个整数 $\hat c_{i, j}$（$0 \le \hat c_{i, j} \le 10^5$；对于任意 $i$，至少有一个 $\hat c_{i,j} > 0$）——已分配给第 $i$ 个主题第 $j$ 个项目的资金金额；接着是 $n_i$ 个整数 $p'_{i,j}$（$1 \le p'_{i,j} \le 1000$）——它们决定了 $p_{i,j}$ 的值，计算公式为 $p_{i, j} = {p'_{i, j}} \big/ {\sum\limits_{j=1}^{n_i}{p'_{i, j}}}$，且 $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$。 最后一行包含 $q$ 个整数 $x_k$（$0 \le x_k \le 10^{12}$）——第 $k$ 种可能的额外资金金额。

输出 $q$ 个实数——对应额外资金 $x_k$ 的最小可能非最优性。答案的绝对或相对误差不得超过 $10^{-6}$。

翻译由 DeepSeek V3 完成