题目链接：https://nanti.jisuanke.com/t/39271
题意：给定n个物品，m组限制，每个物品有个伤害值，现在让两个人取完所有物品，要使得两个人取得物品伤害值之和最接近，输出伤害值不小于另一个的人的伤害值，每组限制包括两次数x y，表示物品x和物品y不能由同一个人取得。
思路：思路是通过bfs或并查集将有关系的物品合并为一个物品，合并的物品有两个值，每个人必须分别取每个物品的一个值，然后就是背包问题了。
具体实现就是用root[i]表示i的祖先，a[i]表示i与其祖先的关系（为0表示和祖先放在一边，为1表示和祖先不能放一边），可以得到(x->z=(x->y)^(y->z)，x->z表示物品x,z的关系,还有x->y=y->x)，然后就可以通过并查集来维护所有限制关系。之后遍历所有祖先等于自己的个数，即合并后的连通块个数，设为k。然后把第i个集合中和与祖先关系为0的都加在b[i][0]上，把第i个集合中和祖先关系为1的都加在b[i][1]上。然后还有个操作就是因为每个人分别取b[i][0],b[i][1]中的一个，要使差值最小，那么可以将b[i][0],b[i][1]同时减一个数使得min(b[i][0],b[i][1])=0，这并不影响答案。这样就是减去min(b[i][0],b[i][1])=0，剩下那个非0的数存进d[i]中，并且将所有d[i]加起来得到sum1。
那么问题就转换为有k个物体，价值为d[i]，这里价值和体积一样，在空间为sum/2的背包中，每次有选或不选两种可能，求背包最大的价值为多少。然后就可以得到结果了。说的有点绕，但思路不复杂，理解一下自己写写，代码写得有点乱，不建议看。。
AC代码：
#include<cstdio> #include<map> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int T,n,m,sum1,sum2,sum3,sum4,c[205],root[205],a[205]; int b[205][2],d[205],dp[50005]; int getr(int k){ if(root[k]==k) return k; else{ int tmp=root[k]; root[k]=getr(root[k]); a[k]^=a[tmp]; return root[k]; } } int main(){ scanf("%d",&T); while(T--){ memset(b,0,sizeof(b)); memset(d,0,sizeof(d)); memset(dp,0,sizeof(dp)); sum1=0,sum2=0,sum3=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) root[i]=i,a[i]=0; for(int i=1;i<=n;++i) scanf("%d",&c[i]),c[i]/=100,sum1+=c[i]; while(m--){ int x,y,rx,ry; scanf("%d%d",&x,&y); rx=getr(x),ry=getr(y); if(rx==ry) continue; root[ry]=rx; a[ry]=1^a[y]^a[x]; } map<int,int> mp; int k=0; for(int i=1;i<=n;++i) if(getr(i)==i) mp[i]=++k; for(int i=1;i<=n;++i){ int r=getr(i); b[mp[r]][a[i]]+=c[i]; } for(int i=1;i<=k;++i) d[i]=abs(b[i][0]-b[i][1]),sum2+=d[i],sum3+=min(b[i][0],b[i][1]); sum4=sum2/2; for(int i=1;i<=k;++i) for(int j=sum4;j>=d[i];--j) dp[j]=max(dp[j],dp[j-d[i]]+d[i]); printf("%d ",(sum1-(sum3+dp[sum4]))*100); } return 0; }