西安邀请赛-D（带权并查集+背包）-白红宇

西安邀请赛-D（带权并查集+背包）

阅读量：6164 次

发布时间：2019-06-21

本文共 2120 字，大约阅读时间需要 7 分钟。

题目链接：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
     
      #include
      #include
       
        #include
        
         #include
         
          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
          
            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\n",(sum1-(sum3+dp[sum4]))*100); } return 0;}

转载于:https://www.cnblogs.com/FrankChen831X/p/10927305.html

你可能感兴趣的文章