Miku and Generals-2019西安邀请赛 D(二分图+背包)

题目链接

https://nanti.jisuanke.com/t/39271

题目大意

n个数和m个关系,每一对关系(a,b)代表第a个数与第b个数不能被分到同一组里,现在要对这n个数分组,问分成的两组的和的差最小可以是多少。

解题思路

先用二分图处理这m个关系,染色后假设每组小的分为一组,大的为另一组,如果只看小的这一组,那么交换某些组,就相当于给小的一组加上他们的差值,比如a,b两组,a<b交换a,b对a来说就相当于是变成了a+(b-a)。

如果总和为2x 那么每组为x是最优的,每组小的和为y ,那么只要找小于(x-y)的最大的即最优解,01背包即可解决。

代码

#include <bits/stdc++.h>
struct node{
    int v,next;
}edge[450];
using namespace std;
int a[220],head[220],vis[220],b[220],dp[220000];
int top,si;
void add(int u,int v){
    edge[top]={v,head[u]};
    head[u]=top++;
}
void dfs(int x,int op){
    vis[x]=si+op;
    for(int i=head[x];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v]==0){
            if(op==0)dfs(v,1);
            else dfs(v,0);
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int num=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]/=100;
            num+=a[i];
        }
        memset(head,-1,sizeof(head));
        top=0;
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        memset(vis,0,sizeof(vis));
        si=1;
        for(int i=1;i<=n;i++){
            if(vis[i]==0){
                dfs(i,0);
                si+=2;
            }
        }
        si--;
        memset(b,0,sizeof(b));
        int sum=0;
        for(int i=1;i<=n;i++){
            b[vis[i]]+=a[i];
        }
        int p=1;
        for(int i=1;i<=si;i+=2){
            sum+=min(b[i],b[i+1]);
            b[p++]=abs(b[i]-b[i+1]);
        }
        memset(dp,0,sizeof(dp));
        m=(num+1)/2;
        m-=sum;
        dp[0]=0;
        for(int i=1;i<p;i++){
            for(int j=m;j>=b[i];j--){
                dp[j]=max(dp[j],dp[j-b[i]]+b[i]);
            }
        }
        int x=sum;
        if(dp[m]!=-1){
            x+=dp[m];
        }
        int y=num-x;
        cout<<max(x,y)*100<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注