记录编号	108499	评测结果	AAAAAAAAAA
题目名称	机器人搬运	最终得分	100
用户昵称	→震世逆空波→	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2014-07-04 20:34:46	内存使用	4.13 MiB

#include <cstring>
#include <cstdio>

const int max_n=1001;

using namespace std;

int n,w0,k;
int a,b;
int p[max_n];//price 
int w[max_n];//weight 
int fa[max_n];//father 
int f[max_n];//f[w]值 
int t[max_n][max_n];//分组记录 

void in();
void out();
void Union(int x,int y);
void bag();
int find_f(int x);

int main()
{
	freopen("robots.in","r",stdin);
	freopen("robots.out","w",stdout);
	
	in();
	out();
	return 0;
}

void in()
{
	scanf("%d%d%d",&n,&w0,&k);
	for (int i = 1 ; i <= n ; i ++ )
	{
		scanf("%d%d",&p[i],&w[i]);
		fa[i]=i;
	}
	while( k -- )
	{
		scanf("%d%d",&a,&b);
		Union(a,b);
	}
	for (int i = 1;i<=n;i ++ )
	{
		a=find_f(i);
		t[a][++t[a][0]]=i;
	}
}

void out()
{
	bag();
	printf("%d\n",f[w0]);
}

void bag()
{
	for (int k = 1;k <= n;k ++ )
	{
		if (t[k][0] > 0)
		{
			for (int j = w0;j >= 0;j --)
			{
				for (int i = 1 ;i <= t[k][0];i ++ )
				{
					a = t[k][i];
					if (j>=w[a] && f[j]<f[j-w[a]]+p[a])
						f[j]=f[j-w[a]]+p[a];
				}
			}
		}
	}
}

void Union(int x,int y)
{
	int r1=find_f(x);
	int r2=find_f(y);
	if (r1 != r2) fa[r2]=r1;
}

int find_f(int x)
{
	if (fa[x] == x)return x;
	fa[x]=find_f(fa[x]);
	return fa[x];
}