记录编号	242667	评测结果	AAAAAAAAAA
题目名称	搭配购买	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.271 s
提交时间	2016-03-28 06:15:44	内存使用	0.52 MiB

#include<cstdio>
const int maxn=10005;
int v[maxn],w[maxn];
int ufs[maxn],totw[maxn],totv[maxn];
int find(int x){
    return x==ufs[x]?x:ufs[x]=find(ufs[x]);
}
void link(int a,int b){
    int ra=find(a),rb=find(b);
    if(ra!=rb){
        ufs[ra]=rb;
        totw[rb]+=totw[ra];
        totv[rb]+=totv[ra];
    }
}
int f[10005];
int max(int a,int b){
    return a>b?a:b;
}
int main(){
	freopen("buy.in","r",stdin);
	freopen("buy.out","w",stdout);
    int n,m,money;
    scanf("%d %d %d",&n,&m,&money);
    for(int i=1;i<=n;++i){
        scanf("%d %d",totw+i,totv+i);
    }
    for(int i=1;i<=n;++i)ufs[i]=i;
    int a,b;
    for(int i=1;i<=m;++i){
        scanf("%d %d",&a,&b);
        link(a,b);
    }
    int len=0;
    for(int i=1;i<=n;++i){
        if(ufs[i]==i){
            w[++len]=totw[i];
            v[len]=totv[i];
        }
    }
    for(int i=1;i<=len;++i){
        for(int j=money;j>=w[i];--j){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
    printf("%d",f[money]);
	fclose(stdin);fclose(stdout);
	return 0;
}