AGC043F

首先排序使得 \(S_{i,1}\le S_{i,2}\le \dots \le S_{i,k_i}\)。

记 \(x_{i,j}\) 表示第 \(i\) 家珠宝店的前 \(j-1\) 种珠宝被选择的次数之和，那么有：

可以发现以上就是原问题的充要条件，最终要求最小化 \(\sum_{i,j}p_{i,j}(x_{i,j+1}-x_{i,j})\)，

与上一个问题基本相同，可以写作以下形式：

对偶后变成最小费用流，对 \((i,1)\) 的出度减入度要求为 \(+\infty\)，其余点要求流量平衡。前 \(2\) 个 \(\sum\) 以及最后一个 \(\sum\) 都正常连边即可，第 \(4\) 个 \(\sum\) 可以看作 \(x_{i,k_i+1}-x_{i,1}-A\)，于是相当于从 \((i,1)\) 向 \((i,k_i+1)\) 连流量为 \(+\infty\)，费用为 \(A\) 的边；从 \((i,k_i+1)\) 向 \((i,1)\) 连流量为 \(+\infty\)，费用为 \(-A\) 的边。因此可以将 \((i,1)\) 作为源点，\((i,k_i+1)\) 向汇点连费用为 \(-A\) 的边，就变成一个最小费用流问题了。

对于多组询问，考虑最终的费用中，\(A\) 只在 \((i,k_i+1)\) 连向汇点的边上作为费用，并且所有连向汇点的边的费用均为 \(-A\)，因此最终答案一定形如 \(A\times flow-C\) 的形式，其中 \(flow\) 为流量，\(C\) 为此时其他边的费用。注意到最小费用流的过程形如不断跑最短路，跑出 \(A=0\) 时的 \(dis_t\)，如果 \(dis_t\ge A\) 那么就终止，否则将本次增广的流加入答案。因此可以预处理出 \(A=0\) 时每次跑出的 \(dis_t\)，以及此时的流量及费用，那么对于每组询问可以通过二分找到对应的 \(flow\) 为多少，即可回答询问。