不是VIP会员,不能显示答案

1928 【基础】采购礼品

时间限制: 1 Sec 内存限制: 128 MB
题目描述:
王老师来到商店为同学们采购礼品。这家店有n种礼品(编号是1~n),每种礼品只有1件。老板为了促销,对礼品进行搭配销售,有关联性的礼品必须都要采购(奇怪的规定),比如1号礼品和3号礼品搭配了,3号和8号礼品搭配了,那么王老师想要买1号礼品的话,就需要把3号和8号礼品都买了。现给定每种礼品的价钱和价值,请问在有限的钱w的情况下,能够买到礼品的最大价值是多少?
输入: 第一行输入三个整数,n,m,w,表示有n种礼品,m个搭配和你现有的钱的数目。
第二行至n+1行,每行有两个整数,c、d,表示第i种礼品的价钱和价值。
第n+2至n+1+m行 ,每行有两个整数,u、v,表示u号礼品和v号礼品是有关联的,已经形成搭配销售的关系。
1≤n,w≤10^4,0≤m≤5×10^3。
输出: 一行,表示可以获得的最大价值。
样例输入:
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
样例输出:
1
提示:
来源: 背包
解答: 背包