← 返回题单

题单练习并查集

← 上一题下一题 →

A70726 | $采购礼品$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

王老师来到商店为同学们采购礼品。 这家店有 n 种礼品（编号是 1 \sim n ），每种礼品只有 1 件。老板为了促销，对礼品进行搭配销售，有关联性的礼品必须都要采购（奇怪的规定），比如 1 号礼品和 3 号礼品搭配了，3 号和 8 号礼品搭配了，那么王老师想要买 1 号礼品的话，就需要把 3 号和 8 号礼品都买了。 现给定每种礼品的价钱和价值，请问在有限的钱 w 的情况下，能够买到礼品的最大价值是多少？

输入格式

第一行输入三个整数，n,m,w，表示有 n 种礼品，m 个搭配和你现有的钱的数目。 第二行至 n+1 行，每行有两个整数，c、d，表示第 i 种礼品的价钱和价值。（1≤c,d≤10^5） 第 n+2 至 n+1+m 行 ，每行有两个整数，u、v，表示 u 号礼品和 v 号礼品是有关联的，已经形成搭配销售的关系。 数据范围： 1≤n,w≤10^4,0≤m≤5 \times 10^3。

输出格式

一行，表示可以获得的最大价值。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出