[vijos1250]最勇敢的机器人

题目（vijos）
这题一看就知道是个分组背包......
只不过这个“组”换成了集合而已，
所以用并查集搞搞就行。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,m,k;
int f[1005];
int p[1005],w[1005];
int dp[1005];
int cnt[1005];
int zu[1005][1005];
int find(int e)
{
	return e==f[e]?e:f[e]=find(f[e]);
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;++i) f[i]=i;
	for (int i=1;i<=n;++i)
		scanf("%d%d",&p[i],&w[i]);
	for (int i=1;i<=k;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int px=find(x),py=find(y);
		if (px!=py) f[px]=py;
	}
	for (int i=1;i<=n;++i)
	{
		int u=find(i);
		cnt[u]++;
		zu[u][cnt[u]]=i;
	}
	for (int i=1;i<=n;++i)
	{
		if (!cnt[i]) continue;
		for (int j=m;j>=0;--j)
		{
			for (int k=1;k<=cnt[i];++k)
			{
				if (j>=w[zu[i][k]])
					dp[j]=max(dp[j],dp[j-w[zu[i][k]]]+p[zu[i][k]]);
			}
		}
	}
	printf("%d",dp[m]);
	return 0;
}