记录编号	533183	评测结果	WWWWWWWWWW
题目名称	机器人搬运	最终得分	0
用户昵称	Deacep	是否通过	未通过
代码语言	C++	运行时间	0.051 s
提交时间	2019-06-18 20:36:40	内存使用	21.38 MiB

#include<bits/stdc++.h>
using namespace std;
int n,wmax,k;
short to=1,par[1005],a[1005],W[1005],P[1005],w[1005][1005],p[1005][1005],lim[1005];
int f[1005][1005];
void init(){
	for(int i=1;i<=n;i++)
	par[i]=i;
}
int rot(int x){
	if(par[x]!=x)
	return par[x]=rot(par[x]);
}
void merg(int x,int y){
	if(rot(x)!=rot(y))
	par[par[y]]=par[x];
}
void date(){
	memset(f,0,sizeof(f));
	memset(a,0,sizeof(a));
	int i;
	for(i=1;i<=n;i++)
	lim[i]=1;
	init();
	cin>>n>>wmax>>k;
	for(i=1;i<=n;i++)
	cin>>P[i]>>W[i];
	for(i=1;i<=k;i++){
		int u,v;
		cin>>u>>v;
		merg(u,v);
	}
	for(i=1;i<=n;i++){
		if(!a[par[i]])
		a[par[i]]=to++;
		else
		a[i]=a[par[i]];
		w[a[i]][lim[i]]=W[i];
		p[a[i]][lim[i]++]=P[i];
	}
}
void _work(){
	date();
	for(int i=1;i<to;i++){
		for(int j=wmax;j>=0;j--){
			f[i][j]=f[i-1][j];
			for(int k=1;k<lim[i];k++){
				if(j-w[i][k]>=0){
					f[i][j]=max(f[i][j],f[i-1][j-w[i][k]]+p[i][k]);
				}
			}
		}
	}
	cout<<f[to-1][wmax];
	return;
}
int main(){
	freopen("robots.in","r",stdin);
	freopen("robots.out","w",stdout);
	_work();
	return 0;
}