C++ 搭配购买

题目描述

Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有nn朵云，云朵被编号为1，2，…，n1，2，…，n并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第1行n，m，n，w表示n朵云，m个搭配，Joe有w的钱。

第22 ~ n+1行，每行c_ici​，d_idi​表示ii朵云的价钱和价值。

第n+2 ~ n+1+m行，每行u_i，v_i，表示买u_i就必须买v_i，同理，如果买v_i​就必须买u_i​。

输出格式

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

样例

输入样例

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

输出样例

1

代码如下：

#include 
using namespace std;
const int maxn = 10005;
int c[maxn], d[maxn], e[maxn], f[maxn];
int ans(int x){
	if(f[x] == 0){
		return x;
	}
	return f[x] = ans(f[x]);
}
void dfs(int x, int y){
	int x1 = ans(x), y1 = ans(y);
	if(x1 != y1){
		f[y1] = x1;
		c[x1] += c[y1];
		d[x1] += d[y1];
		c[y1] = 0;
		d[y1] = 0;
	}
}
int main(){
	int n, m, w, a, b;
	cin >> n >> m >> w;
	for(int i = 1; i <= n; i++){
		cin >> c[i] >> d[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		dfs(a, b);
	}
	for(int i = 1; i <= n; i++)
		if(c[i] != 0)
			for(int j = w; j >= c[i]; j--) 
				e[j] = max(e[j], e[j-c[i]] + d[i]); 
			cout << e[w]; 
	return 0;
}