題目?
Joe覺得云朵很美，決定去山上的商店買一些云朵。
商店里有?n?朵云，云朵被編號為?1,2,…,n，并且每朵云都有一個價值。
但是商店老板跟他說，一些云朵要搭配來買才好，所以買一朵云則與這朵云有搭配的云都要買。
但是Joe的錢有限，所以他希望買的價值越多越好。
輸入格式
第?11?行包含三個整數?n，m，w，表示有?n 朵云，m?個搭配，Joe有?w?的錢。
第?2～n+1行，每行兩個整數?ci，di 表示?i 朵云的價錢和價值。
第?n+2～n+1+m 行，每行兩個整數?ui，vi，表示買?ui 就必須買?vi，同理，如果買?vi 就必須買?ui。
輸出格式
一行，表示可以獲得的最大價值。
數據范圍
1≤n≤10000
0≤m≤5000
1≤w≤10000
1≤ci≤5000
1≤di≤100
1≤ui,vi≤n
輸入樣例：
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
輸出樣例：
1思路
? ? ? ? 1、初始狀態下，我們可以將每一件物品單獨放到一個集合中，如果購買物品1就要購買物品2則將1，2放入同一個集合中，并且集合的價值等于集合內所有的物品價值之和。如果要買一個物品，則需要購買該物品所屬集合的全部物品。（并查集）
? ? ? ? 2、使用01背包進行處理數據，使得使用給定的金錢買到的物品價值之和最大。（01背包）
01背包的原理在我之前的文章講述過。
代碼
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n,m,vol;
int v[N],w[N];
int p[N];
int f[N];int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m >> vol;for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];for(int i = 0; i <= n; i ++) p[i] = i;for(int i = 0; i < m; i ++){int a,b;cin >> a >> b;int pa = find(a),pb = find(b);if(pa != pb){p[pa] = pb;v[pb] += v[pa];w[pb] += w[pa];}}for(int i = 1; i <= n; i ++){if(p[i] == i){for(int j = vol; j - v[i] >= 0; j --)f[j] = max(f[j],f[j - v[i]] + w[i]);}}cout << f[vol] << endl;return 0;}
)
