当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6636:Milk Candy

题目描述
Calabash is now playing an RPG game on his computer. In this game, there are $n$ unknown numbers $x_1,x_2,\dots,x_n$ and $m$ NPCs selling hints. The $i$-th NPC is selling $c_i$ hints. Each hint contains three integers $l_j,r_j,w_j$, which means Calabash can pay $w_j$ coins to buy this hint, and this hint can tell Calabash the value of $x_{l_j}+x_{l_j+1}+\dots+x_{r_j-1}+x_{r_j}$.

The target of the game is to figure out all the $n$ unknown numbers. Clever Calabash knows how to buy hints optimally, but NPCs are greedy, for the $i$-th NPC, Calabash must buy exactly $k_i$ hints from him. Note that each hint can't be bought more than once.

This problem is much more difficult for Calabash. Please write a program to help Calabash find the cheapest way, or determine it is impossible.
输入解释
The first line of the input contains an integer $T(1\leq T\leq 10)$, denoting the number of test cases.

In each test case, there are two integers $n,m(1\leq n,m\leq 80)$ in the first line, denoting the number of unknown numbers and NPCs.

For the next $m$ parts, there are two integers $c_i,k_i(1\leq k_i\leq c_i)$ in the first line, denoting the number of hints the $i$-th NPC has and the limit for the $i$-th NPC.

For the next $c_i$ lines, each line contains three integers $l_j,r_j,w_j(1\leq l_j\leq r_j\leq n,1\leq w_j\leq 10^6)$, describing each hint offered by the $i$-th NPC.

It is guaranteed that $\sum c_i\leq 80$ in each test case.
输出解释
For each test case, print a single line containing an integer, denoting the minimum number of coins. If there is no solution, output ``$\texttt{-1}$'' instead.
输入样例
2
2 2
1 1
1 2 1
3 2
1 1 10
2 2 100
1 2 1000
2 2
1 1
1 1 1
1 1
1 1 2
输出样例
111
-1
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6636

最后修改于 2020-10-25T23:33:02+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/5000MS(Java/Others) 524288/524288K(Java/Others)