Miku and Generals-西安邀请赛-蒲公英云

Miku and Generals-西安邀请赛

题目：https://nanti.jisuanke.com/t/39271

题意：给你n个权值然你分成两组使他们的权值和的差最小，其中有些点是相互矛盾的，不能分在同一组。

分析：所有点都是100的倍数，可以直接除以100，我们二分图染色，每个联通块只有两种情况，因为确定了一个点的所属集合，相邻点就都确定了，而且只有两个集合，然后dp记录所有组合构成的值，dp[i]表示当前这个差值能不能到达，这个过程可以通过可行性背包来解决。然后找一个最小的差值就可以了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int dp[N],pre[N],c[210],vs[210],t,n,m,sum,s1,s2;
vector<int> e[210];
void dfs(int u,int x) {
    vs[u]=1;
    if(x) s1+=c[u]/100;
    else s2+=c[u]/100;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i];
        if(!vs[v]) dfs(v,x^1);
    }
}
int main()
{
    while(~scanf("%d",&t)) {
        while(t--) {
            sum=0;
            memset(dp,0,sizeof(dp));
            memset(vs,0,sizeof(vs));
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) e[i].clear();
            for(int i=1;i<=n;i++) scanf("%d",&c[i]),sum+=c[i]/100;
            for(int i=1;i<=m;i++) {
                int u,v;
                scanf("%d%d",&u,&v);
                e[u].push_back(v);
                e[v].push_back(u);
            }
            dp[0]=1;
            for(int i=1;i<=n;i++) {
                s1=s2=0;
                if(vs[i]) continue;
                dfs(i,0);
                int ss=abs(s1-s2);
                for(int j=0;j<=sum;j++) {
                    if(!dp[j]) continue;
                    pre[j+ss]=1;
                    if(j>=ss) pre[j-ss]=1;
                    else pre[ss-j]=1;
                }
                for(int i=0;i<=sum;i++) dp[i]=pre[i],pre[i]=0;
            }
            int k=0;
            while(dp[++k]==0);
            printf("%d\n",50*(k+sum));
        }
    }
    return 0;
}