20分大佬救命,感觉自己思路没问题就是做不对
查看原帖
20分大佬救命,感觉自己思路没问题就是做不对
811016
ashore_楼主2022/11/9 19:19

把每个云的数据保存下来,然后用并查集生成一个树,用俩数组:一个是保存总价格,一个保存总价值。 保存的地方就是每个树的根节点索引的位置

#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;
}
2022/11/9 19:19
加载中...