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

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

第一行输入三个整数， 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​ 朵。

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

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

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<

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