70 WA 2 3 10
查看原帖
70 WA 2 3 10
1122193
FarmerDrone楼主2024/6/13 22:41
#include <bits/stdc++.h>
using namespace std;

int c[10050], v[10050], f[10050];

int find(int x) 
{
	if (f[x] == x)
		return x;	
	return f[x] = find(f[x]);
}

int main()
{
	int m, V, n, s, t;
	cin >> n >> m >> V;
	for (int i = 1; i <= n; i++)
		cin >> c[i] >> v[i], f[i] = i;
	vector <int> vc, vv;
	while (m--)
	{
		cin >> s >> t;
		if (find(s) != find(t))	
			f[s] = t;
	}
	for (int i = 1; i <= n; i++)
		if (find(i) != i)
			c[find(i)] += c[i], v[find(i)] += v[i];
	for (int i = 1; i <= n; i++)
		if (find(i) == i)
			vc.push_back(c[i]), vv.push_back(v[i]);
	int dp[V + 1] = {};
	int sz = vc.size();
	for (int i = 0; i < sz; i++)
		for (int j = V; j >= vc[i]; j--)
			dp[j] = max(dp[j], dp[j - vc[i]] + vv[i]);//, cout << dp[j] << (j > vc[i] ? " " : "\n");
	cout << dp[V] << endl; 
	return 0;
}
2024/6/13 22:41
加载中...