首页 > 代码库 > hdu 5076 最小割灵活的运用

hdu 5076 最小割灵活的运用

题意比较复杂,其实关键是抽象出来:每个点,可以赋予俩个值(二选一,必需选一个,设ai,bi)。  求所有之和最大,有条件:若俩个点同时满足:

1,:点的二进制只有一位不同。  2:至少有一个是选B值; 则可获得对应加成。

这题开始想了半天,建图遇到问题,看了官方说是最小割,于是入手:

a值就是小于阈值的最大值,B值就是大于等于的最大值。

思路:俩个点选其一,必然想到建二分(每个点一分为二)图,中间连无穷的边。因为只有一位不同,必然分奇偶点,有奇数个1的点,源点到他为A值,对应点到汇点为B值,偶点相反。然后下面奇点向偶点中只有一位不同的点连边,为(ui^uj)。理由:先所有值都取,舍去最小割,便是答案。当都选A值的时候,那么附加的值就不能取了,必是要成为割边,这也是分奇数偶数连发不同的原因,这恰好把同侧的关系分到异侧了。题目只要方案,不要最值。有负数,先都加2014.  ans=所有权之和-最小割-n*1024。

#include<iostream> //15MS
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,nn,mm,ss,tt;
const int inf=0x3f3f3f3f;
const int maxn=1025,maxe=780000;
int rge[maxn];int ui[maxn];
int a[maxn][maxn];
struct xy
{
    int low,high;
};
xy dian[maxn];
int head[maxn];int nume=0;int e[maxe][3];
void inline adde(int i,int j,int w)
{
     e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;
     e[nume++][2]=w;
     e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;
     e[nume++][2]=0;
}
int has1(int i)
{
    int ant=0;
    while(i)
    {
        if(i&1)ant++;
        i=(i>>1);
    }
    return ant;
}
void build()
{
    for(int i=0;i<nn;i++)
    {
      adde(i+1,i+nn+1,inf);
      if(has1(i)&1)
      {
          if(dian[i].low!=-1)
           adde(ss,i+1,a[i][dian[i].low]);
          else
           {
               adde(ss,i+1,0);
           }
          adde(i+nn+1,tt,a[i][dian[i].high]);
          for(int j=0;j<nn;j++)
          {
              if(has1(j^i)==1)
              {
                adde(i+1,1+j+nn,ui[i]^ui[j]);
              }
          }
      }
      else
      {
          if(dian[i].low!=-1)
           adde(i+nn+1,tt,a[i][dian[i].low]);
          else
           {
               adde(i+nn+1,tt,0);
           }
          adde(ss,i+1,a[i][dian[i].high]);
      }
    }
}
int vis[maxn];int lev[maxn];
bool bfs()
{
    for(int i=0;i<tt+2;i++)
        lev[i]=vis[i]=0;
    queue<int>q;
    q.push(ss);
    vis[ss]=1;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        for(int j=head[cur];j!=-1;j=e[j][1])
        {
            int v=e[j][0];
            if(!vis[v]&&e[j][2]>0)
            {
                vis[v]=1;
                lev[v]=lev[cur]+1;
                q.push(v);
            }
        }
    }
    return vis[tt];
}
int dfs(int cur,int minf)
{
    if(cur==tt||minf==0)return minf;
    int sumf=0,f;
    for(int j=head[cur];j!=-1&&minf;j=e[j][1])
        {
            int v=e[j][0];
            if(lev[v]==lev[cur]+1&&e[j][2]>0)
            {
                f=dfs(v,e[j][2]<minf?e[j][2]:minf);
                minf-=f;sumf+=f;
                e[j][2]-=f;e[j^1][2]+=f;
            }
        }
    if(!sumf) lev[cur]=-1;
    return sumf;
}
int dinic()
{
    int sums=0;
    while(bfs())
    {
        sums+=dfs(ss,inf);
    }
    return sums;
}
void init()
{
     scanf("%d%d",&n,&m);
      nn=(1<<n),mm=(1<<m);
      ss=0,tt=2*nn+1;
      for(int i=0;i<=tt+1;i++)
       {
           head[i]=-1;
       }
      nume=0;
     for(int i=0;i<nn;i++)
        scanf("%d",&rge[i]);
    for(int i=0;i<nn;i++)
       scanf("%d",&ui[i]);
    for(int i=0;i<nn;i++)
      for(int j=0;j<mm;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]+=1024;
        }
   for(int i=0;i<nn;i++)
      {
            dian[i].low=-1;
            int max1=0,max2=0;
          for(int j=0;j<rge[i];j++)
          {
              if(a[i][j]>max1){max1=a[i][j];dian[i].low=j;}
          }
           for(int j=rge[i];j<mm;j++)
          {
             if(a[i][j]>max2){max2=a[i][j];dian[i].high=j;}
          }
      }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
       init();
       build();
       dinic();
       for(int i=1;i<nn;i++)
         if(vis[i]&&(has1(i-1)&1)||!vis[i]&&!(has1(i-1)&1))
             printf("%d ",dian[i-1].low);
         else
             printf("%d ",dian[i-1].high);
         if(vis[nn]&&(has1(nn-1)&1)||!vis[nn]&&!(has1(nn-1)&1))
             printf("%d\n",dian[nn-1].low);
         else    printf("%d\n",dian[nn-1].high);
    }
    return 0;
}




hdu 5076 最小割灵活的运用