题目描述
joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n多云，云朵被编号为1，2，……，n，并且每朵云都有一个价值。但商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这多云有搭配的云都要买。但是Joe 的钱有限，所以他希望买的价值越多越好。
输入
第一行n，m，w，表示n多云，m个搭配，Joe有w的钱
第二只n+1行，每行ci，di表示i朵云的价钱和价值
第n+2值n+1+m行，每行ui和vi表示买ui就必须买vi，同理，如果买vi就必须买ui
输出
一行，表示可以获得的最大价值
样例输入
5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2
样例输出
1
提示
n<=10000,m<=5000,w<=10000
题解：
此题很水，但是我却看错了题目，想到了另一种题目类型决定把这种也说说.
先讲此题：
这题意是有关联的要买就都买，于是用并查集合并，然后背包.
接下来是另一种：
我以为是拓扑序，买完这个就不买他的下层.
也就是说1->2->3可以只买2.3不买1
于是想到dfs一边，把所有的购买方案都看作一个物品（3，23，123）然后再背包
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
struct node{
int w,val;
}a[N];
int fa[N],F[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int w[N],v[N],tot=;
int main()
{
//freopen("pp.in","r",stdin);
int n=gi(),m=gi(),k=gi(),x,y;
for(int i=;i<=n;i++)a[i].w=gi(),a[i].val=gi(),fa[i]=i;
for(int i=;i<=m;i++)
{
x=gi();y=gi();
a[find(x)].val+=a[find(y)].val;
a[find(x)].w+=a[find(y)].w;
fa[find(y)]=find(x);
}
for(int i=;i<=n;i++)if(fa[i]==i){w[++tot]=a[i].w;v[tot]=a[i].val;}
for(int i=;i<=tot;i++)
{
for(int j=k;j>=w[i];j--)
{
F[j]=max(F[j-w[i]]+v[i],F[j]);
}
}
printf("%d",F[k]);
return ;
}