Miku and Generals-西安邀请赛

拼搏现实的明天。 2022-04-25 07:04 215阅读 0赞

## 题目：[https://nanti.jisuanke.com/t/39271][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;
    }

[https_nanti.jisuanke.com_t_39271]: https://nanti.jisuanke.com/t/39271