P1455 搭配购买
题意：就是说有n朵云，每朵云有自己的价钱（重量）和价值（价值），还有我自己现在有钱的数目（背包），然后还告诉你，哪几朵云是属于捆绑销售的，我们在面对捆绑销售要一次性买了，因而我们可以看出来，这题其实就是并查集+01背包，并查集体现在捆绑销售，连通性问题
思路：先用并查集将所有云进行连通，将连通的物品的价钱和价值累加到一个元素里面，然后进行01背包就可以秒了
#include<bits/stdc++.h>
using namespace std;
int n,m,W;
int w[10005];
int v[10005];
int f[10005];//并查集数组
int dp[10005];
int cha(int x)
{if(f[x]==x){return x;}f[x]=cha(f[x]);//路径压缩return f[x];
}void bing(int x,int y)
{f[cha(x)]=cha(y);//并结点操作
}
int main()
{cin>>n>>m>>W;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=n;i++){cin>>w[i]>>v[i];}int a,b;for(int i=1;i<=m;i++){cin>>a>>b;bing(a,b);}for(int i=1;i<=n;i++){if(f[i]!=i)//将捆绑在一起的都归并到根结点上{w[cha(i)]+=w[i];v[cha(i)]+=v[i];}}for(int i=1;i<=n;i++){for(int j=W;j>=w[i];j--){if(f[i]==i){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}}cout<<dp[W];return 0;
} P2170 选学霸
题意：就是说，在n个人中选m个人当学霸，但是有k对人实力相当，要选就要一起选上，问你选的人和预期差多少（绝对值差）
思路：还是连通性问题，并查集+01背包，然后我们可以先用并查集将这个k对人都先并起来，然后对所有根结点进行01背包操作（需要注意的地方就是背包容量为2*m，因为可大可小，问的是绝对值的差）
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int dp[40004];
int f[40004];
int num[40004];
int cha(int x)
{if(f[x]==x)return x;f[x]=cha(f[x]);return f[x];
}void bing(int x,int y)
{f[cha(x)]=cha(y);
}int main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=n;i++)num[i]=1;int a,b;for(int i=1;i<=k;i++){cin>>a>>b;bing(a,b);}for(int i=1;i<=n;i++){if(f[i]!=i){num[cha(i)]+=num[i];}}for(int i=1;i<=n;i++){for(int j=2*m;j>=num[i];j--){if(f[i]==i){dp[j]=max(dp[j],dp[j-num[i]]+num[i]);}}}int ans=0x3f3f3f3f;int sum=0x3f3f3f3f;for(int i=1;i<=2*m;i++){if(abs(dp[i]-m)<ans){ans=abs(dp[i]-m);sum=dp[i];}}if(sum==0x3f3f3f3f)cout<<0;elsecout<<sum;return 0;
}
