hdu 5076 最小割灵活的运用

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

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

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

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

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

#include
  
    //15MS
#include
   
     #include
    
      #include
     
       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
      
       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]
       
        max1){max1=a[i][j];dian[i].low=j;} } for(int j=rge[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