50分玄关
查看原帖
50分玄关
1665658
OkoukiO楼主2025/6/29 00:16
#include <bits/stdc++.h>
using namespace std;
#define in cin
#define out cout
#define int long long
const int N = 1e4 + 5;
int fa[N], n, m, y, c[N], d[N];
int get(int x) {
	if (fa[x] == x)
		return x;
	return fa[x] = get(fa[x]);
}
struct node {
	int c, d;
} coin[N];
void merge(int x, int y) {
	fa[get(x)] = get(y), coin[get(x)].c += coin[get(y)].c, coin[get(x)].d += coin[get(y)].d;
}
int dp[N], v[N], w[N], wid, vid;
int Dp() {
	for (int i = 1; i <= vid; i++)
		for (int j = y; j >= v[i]; j--)
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
	return dp[y];
}
signed main() {
	in >> n >> m >> y;
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= n; i++)
		in >> coin[i].c >> coin[i].d;
	while (m--) {
		int a, b;
		in >> a >> b;
		merge(a, b);
	}
	for (int i = 1; i <= n; i++)
		if (coin[get(i)].c <= y)
			v[++vid] = coin[get(i)].c, w[++wid] = coin[get(i)].d;
	out << Dp();
	return 0;
}
2025/6/29 00:16
加载中...