11月15日星期六18:30-21:30

S+01Z04【基础】采购礼品背包并查集

描述

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

输入描述

第一行输入三个整数，n,m,w，表示有n种礼品，m个搭配和你现有的钱的数目。

第二行至n+1行，每行有两个整数，c、d，表示第i种礼品的价钱和价值。（1≤c,d≤105）

第n+2至n+1+m行，每行有两个整数，u、v，表示u号礼品和v号礼品是有关联的，已经形成搭配销售的关系。

1≤n,w≤104,0≤m≤5×103。

输出描述

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

用例输入 1

用例输出 1

代码

S+01Z02 比赛组队

描述

有一场数学团体赛，学校要从n个人中选出m个人组队参赛，这m个人中有k对人本身在校内就是一个团队的，因此在一个团对的同学要么都选，要么都不选。请你编程选出尽可能和m接近的人数。

输入描述

第一行，三个正整数n,m,k。

第2至第k行,每行2个数，表示在校内就在一个团队的2个人的编号（编号为1,2,…,n）。

1≤n,m≤2×104。

输出描述

一行，与原来的m尽可能接近的选出的人数。

如果有两种方案与m的差的绝对值相等，选较小的一种。

用例输入 1

4 3 2
1 2
3 4

11月15日星期六18:30-21:30

S+01Z04【基础】采购礼品 背包并查集#

描述#

输入描述#

输出描述#

用例输入 1#

用例输出 1#

代码#

S+01Z02 比赛组队#

描述#

输入描述#

输出描述#

用例输入 1#

用例输出 1#

代码#

S+01Z04【基础】采购礼品背包并查集

描述

输入描述

输出描述

用例输入 1

用例输出 1

代码

S+01Z02 比赛组队

描述

输入描述

输出描述

用例输入 1

用例输出 1

代码