题目链接：
https://nanti.jisuanke.com/t/39271
题意：
给你n个物品，要把这n个物品分成两堆。然后给了m个对立关系，比如a和b对立，那么a和b不能同一堆中。
然后要使这两堆物品价值的差值尽可能小，输出物品价值大的那一堆的那个值。
输入描述：
t组样例，t<=10
0<=n,m<=200;
n个物品，0<=a[i]<=5*10^4; 并且a[i]是100的倍数
然后输入m对对立关系
样例：
输入：
1
4 2
1400 700 2100 900
1 3
3 4
输出
2800
题解
首先每个物品都是100的倍数，那么可以先将a[i]都除以100，算出答案后乘100。
然后用图染色处理对立物品，把必须同时选的物品合并成一个，比如第一个样例1 3对立， 3 4对立，那么1和4肯定要同时选。
把对立物品的价值放到一个结构体里。
然后就是01背包问题了，用sum/2为背包容量，看最多能放多少价值的东西。最后答案就是（sum-dp[sum/2]）*100
sum是奇数或者偶数没有影响，用背包算的就是价值较小的那堆的物品最多能放多少。奇数的话较小那堆对多也只能放sum/2价值的物品。
dp两种转移方式：
1.如果这个物品有独立物品，那么这两个必须选一个。
2.如果这个物品没有对立物品，那么可以选也可以不选。
输入的数据物品价值a[i]可能为0，这道题的一个坑点。
背包大小是sum/2. 数组开50000就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=204;
const int N=5e4+5;
int head[maxn],nex[maxn*2],to[maxn*2],cnt;
int color[maxn];
int v,w;
int dp[N];
int a[maxn];
struct node{
int v,w;
}c[maxn];
void add(int i,int j){
to[++cnt]=j;nex[cnt]=head[i];head[i]=cnt;
}
void dfs(int u,int x){
color[u]=x;
if(x==0){
if(v==-1) v=0;
v+=a[u];
}
else {
if(w==-1) w=0;
w+=a[u];
}
for(int i=head[u];~i;i=nex[i]){
int j=to[i];
if(color[j]==-1) dfs(j,!x);
}
}
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
memset(head,-1,sizeof head);
memset(color,-1,sizeof color);
memset(dp,0,sizeof dp);
cnt=0;
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",a+i);
a[i]/=100;
sum+=a[i];
}
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
int tot=0;
for(int i=1;i<=n;i++){
if(color[i]==-1){
v=-1,w=-1; //物品价值可能为0，所以先初始化成-1，如果最后w还是-1，说明这个物品没有对立物品
//v记录颜色为0的物品价值之和，w记录颜色为1的物品价值之和。
dfs(i,0);
c[tot].v=v;
c[tot].w=w;
tot++;
}
}
n=tot,m=sum/2;
for(int i=0;i<n;i++){
for(int j=m;j>=0;j--){
if(c[i].w!=-1){ //有对立物品，必须从c[i].v和c[i].w选一个
if(j>=c[i].v&&j>=c[i].w) dp[j]=max(dp[j-c[i].v]+c[i].v,dp[j-c[i].w]+c[i].w);
else if(j>=c[i].v) dp[j]=dp[j-c[i].v]+c[i].v;
else if(j>=c[i].w) dp[j]=dp[j-c[i].w]+c[i].w;
}else { //c[i].v没有对立物品，可选可不选。
if(j>=c[i].v) dp[j]=max(dp[j],dp[j-c[i].v]+c[i].v);
}
}
}
int ans=(sum-dp[m])*100;
cout<<ans<<endl;
}
return 0;
}
