首页 > 代码库 > 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 最小割灵活的运用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。