#P8354. [2023广东省队集训]珠宝商店

    ID: 8438 传统题 4000ms 512MiB 尝试: 16 已通过: 1 难度: 10 上传者: 标签>图论差分约束动态规划CF3000网络流数学构造排序背包DP

[2023广东省队集训]珠宝商店

珠宝商店

时间限制:4.0s 内存限制:512.0MB

问题描述

有 NN个商店,其中第ii个商店卖KiK_{i}种珠宝,第j(1≤j≤Ki)j(1\le j\le K_{i}) 种珠宝拥有三个独立的属性 (S,P,C)(S,P,C),依次表示重量,价格,数量。 现在有 QQ 次相互独立的询问,每次给定一个 AiA_{i},询问能否构造出 AiA_{i}个“珠宝盒”,如果可以则输出最小花费 (即购买的珠宝价值之和),否则输出−1-1。

一个“珠宝盒”是一个包含NN 个珠宝的盒子,且满足如下条件:

• 盒子内部的第 ii个珠宝从第ii个珠宝商店处购买。 • 满足 MM 条约束:其中第 ii条约束表示盒子内的第 ViV_{i}个珠宝的重量不应超过第 UiU_{i}个珠宝的重量 +Wi+W_{i}。

输入格式

第一行一个整数 NN。接下来 NN 段,第 ii 段描述第ii个商店。 对于第ii段: 第一行一个整数 KiK_{i}。 接下来KiK_{i}行,第jj 行三个整数 Si,j,Pi,j,Ci,jS_{i,j},P_{i,j},C_{i,j},意义如上。 然后一个整数 MM。 接下来 MM 行,每行三个整数 Ui,Vi,WiU_{i},V_{i},W_{i},意义如上。 然后一个整数 QQ。 接下来 QQ 行,每行一个整数 AiA_i。

输出格式

QQ行,表示每个询问的答案。

样例输入

3
2
1 10 1
3 1 1
3
1 10 1
2 1 1
3 10 1
2
1 1 1
3 10 1
2
1 2 0
2 3 0
3
1
2
3

样例输出

3
42
-1

评测用例规模与约定

对于 70% 的数据,Q≤3000Q\le 3000。 对于 100% 的数据:

• 1≤N,Ki≤301\le N,K_{i}\le 30

• 1≤Si,j≤1091\le S_{i,j}\le 10^{9}

• 1≤Pi,j≤301\le P_{i,j}\le 30

• 1≤Ci,j≤10121\le C_{i,j}\le 10^{12}

• 0≤M≤500\le M\le 50

• 1≤Ui,Vi≤N1\le U_{i},V_{i}\le N

• Ui≠ViU_{i}\ne V_{i}

• 0≤Wi≤1090\le W_{i}\le 10^{9}

• 1≤Q≤1051\le Q\le 10^{5}

• 1≤Ai≤3×10131\le A_{i}\le 3\times 10^{13}