搭配购买——C++详解-创新互联

搭配购买 题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 n n n 朵云，云朵已经被老板编号为 1 , 2 , 3 , . . . , n 1,2,3,...,n 1,2,3,...,n，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

创新互联公司主要从事网站设计制作、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务启东,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575输入格式

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

第二行至 n + 1 n+1 n+1 行，每行有两个整数， c i , d i c_i,d_i ci​,di​，表示第 i i i 朵云的价钱和价值。

第 n + 2 n+2 n+2 至 n + 1 + m n+1+m n+1+m 行 ，每行有两个整数 u i , v i u_i,v_i ui​,vi​。表示买第 u i u_i ui​ 朵云就必须买第 v i v_i vi​ 朵云,同理，如果买第 v i v_i vi​ 朵就必须买第 u i u_i ui​ 朵。

输出格式

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

样例 #1 样例输入 #1

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

样例输出 #1

1

提示

• 对于 30 % 30\% 30% 的数据，满足 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100；
• 对于 50 % 50\% 50% 的数据，满足 1 ≤ n , w ≤ 1 0 3 1 \le n, w \le 10^3 1≤n,w≤103， 1 ≤ m ≤ 100 1 \le m \le 100 1≤m≤100；
• 对于 100 % 100\% 100% 的数据，满足 1 ≤ n , w ≤ 1 0 4 1 \le n, w \le 10^4 1≤n,w≤104， 0 ≤ m ≤ 5 × 1 0 3 0 \le m \le 5 \times 10^3 0≤m≤5×103。

算法

这题的算法很简单啊~~ 就是一个普通的01背包+并查集。
01背包和并查集想必大家一定都了如指掌，那么我就不讲了，下面直接上代码：

• 并查集文章（小天狼星自己写的）
• 01背包文章（同上）
• 并查集资源（无需积分/C币）

好了终于可以安心的给出代码了👇

#include//相信不会有人不知道万能头吧~
using namespace std;
int v,n,m,a,b,d[20000],c[20000],w[20000],f[20000];
int fr(int x)		//查找根结点的函数
{if (x!=f[x])
		x=fr(f[x]);
	return x;
}
int main()
{cin >>n >>m >>v;
	for (int i=1;i<=n;i++)
		f[i]=i;				//初始化并查集
	for (int i=1;i<=n;i++)
		cin >>w[i] >>c[i];		//输入价钱和价格
	for (int i=1;i<=m;i++)
	{cin >>a >>b;	//输入要合并的两个云朵
		f[fr(a)]=fr(b);			//合并a，b
	}
	for (int i=1;i<=n;i++)		//关键循环
	{int zx=fr(i);
		if (zx!=i)	//如果自己不是首领/祖先，说明自己的祖先是其他人
		{	w[zx]+=w[i];
			c[zx]+=c[i];	//将自己的数据加入到=祖先那里
			w[i]=1e+6;		//将自己的价格设为大值，让小朋友买不起
		}
	}
	for (int i=1;i<=n;i++) 
		for (int j=v;j>=w[i];j--)
		{	d[j]=max(d[j],d[j-w[i]]+c[i]);		//01背包模板
		}
	cout<

好了，结束！！
这题你学会了吗？

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：搭配购买——C++详解-创新互联
网页地址：http://mswzjz.cn/article/pohje.html