大佬们,为蒻蒻解答一下,为什么不能这么写!!
查看原帖
大佬们,为蒻蒻解答一下,为什么不能这么写!!
874769
fuckinginging楼主2023/4/19 15:30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, v, l, r;
ll f[500050];
ll dp[500050];
ll c[500050];
ll d[500050];
ll w[500050];
ll u[500050];
ll used[500050];
int find(ll x)
{
	if (f[x] != x) f[x] = find(f[x]);
	return f[x];
}
int main() {
	cin >> n >> m >> v;
	for (int i = 1; i <= n; i++)
	{
		f[i] = i;
		scanf("%lld%lld", &c[i], &d[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%lld%lld", &l, &r);
		f[find(l)] = find(r);
	}
	for (int i = 1; i <= n; i++) 
	{
		if (i != find(i))
		{
			c[find(i)] = c[find(i)] + c[i];
			d[find(i)] = d[find(i)] + d[i];
		}
	}
	for (int i = 1; i <= n; i++)
	{
    //if(f[i]==i)这样写就能过
		for (int j = v; j >= c[find(i)]; j--)
		{
			if (!used[find(i)])/*用used标记为什么过不了?*/
			{
				used[find(i)] = 1;
				dp[j] = max(dp[j], dp[j - c[find(i)]] + d[find(i)]);
			}
		}
	}
	printf("%lld", dp[v]);
	return 0;
}
2023/4/19 15:30
加载中...