把每个云的数据保存下来,然后用并查集生成一个树,用俩数组:一个是保存总价格,一个保存总价值。 保存的地方就是每个树的根节点索引的位置
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define MAX_N 0x3f3f3f
using namespace std;
struct cl {
int c, d;
} arr[MAX_N];
int n, m, w;
int par[MAX_N], rak[MAX_N], pri[MAX_N], val[MAX_N];
inline void init(int n) {
for (int i = 1; i <= n; ++i) par[i] = i, rak[i] = 0, pri[i] = 0, val[i] = 0;
}
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void unit(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (rak[x] < rak[y]) {
par[x] = y;
} else {
par[y] = x;
if (rak[x] == rak[y]) ++rak[x];
}
}
inline bool same(int x, int y) { return find(x) == find(y); }
//--------------上面全是并查集代码
void solve() {
for (int i = 1; i <= n; ++i) {
//把所有的值都加给根结点
val[find(i)] += arr[i].d;//d是价值
pri[find(i)] += arr[i].c;//c是价格
}
int value = 0;
for (int i = 1; i <= n; ++i) {
//当总价格小于等于剩余的钱,就比较哪个大
if (pri[i] <= w) value = max(value, val[i]);
}
printf("%d\n", value);
}
int main() {
scanf("%d %d %d", &n, &m, &w);
init(n);
for (int i = 1; i <= n; ++i) {
//读入云的数据
scanf("%d %d", &arr[i].c, &arr[i].d);
}
for (int i = 1; i <= m; ++i) {
int x, y;
//并查集分组
scanf("%d %d", &x, &y);
unit(x, y);
}
solve();
return 0;
}