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;iq;
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];jmax2){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
