题解 | #Chain sales#

这个题目是一道并查集 + dp ，首先先将所有编号相同的用并查集维护一下下然后再用一次01背包就可以

const int N=100010;
int v[N];
int w[N];
int vol;
int p[N];
int dp[N];
int n,m;

int find(int x)
{
	if(p[x] != x)
	{
		p[x] = find(p[x]);
	}
	return p[x];
}
void solve()
{
	ios;
	cin>>n>>m>>vol;
	for(int i = 1 ; i <= n ; i ++ )
	{
		p[i] = i;
		
	}
	
	for(int i = 1 ; i <= n ; i ++ )
	{
		cin>>v[i]>>w[i];
		
	}
	while(m -- )
	{
		int a , b;
		cin>>a>>b;
		int pa = find(a);
		int pb = find(b);
		if(pa != pb)
		{
			v[pb] += v[pa];
			w[pb] += w[pa];
			p[pa] = p[pb];
			
			
		}
	}
	for(int i = 1 ; i <= n ; i ++ )
	{
		if(p[i] == i)
		{
			for(int j = vol ; j >= v[i] ; j -- )
			{
				dp[j] = max(dp[j] , dp[j - v[i]] + w[i]);
				
			}
		}
	}
	cout<<dp[vol];
}
signed main()
{

	solve();
	return 0;
}