首页 > 代码库 > BZOJ4261 : 建设游乐场
BZOJ4261 : 建设游乐场
将图黑白染色，每个点拆成两个点，分别表示水平和竖直方向，再增加一个点以控制流量，那么每个格子都需要找两个方向去连接。
$S$到每个黑点的控制点连边，流量$2$，费用$0$；
控制点向两个方向的点各连两条边，第一条流量$1$，费用$0$，第二条流量$1$，费用$w$；
然后两个方向的点分别向对应白点连边，流量$1$，费用$0$。
这样一来如果这个格子是直轨道，那么会产生$w$的收益，如果是弯轨道，会产生$2w$的收益。
对于白点也类似处理，求出最大费用最大流，如果满流则有解，最大收益为费用减去总收益。
#include<cstdio>const int inf=~0U>>2,N=15010,M=300000,E=155;int n,m,i,j,tmp,flow,ans,cS,cT,a[E][E],b[E][E],id[E][E][3];int u[M],v[M],c[M],co[M],nxt[M],t=1,S,T,l,r,q[M],g[N],f[N],d[N];bool in[N];inline void add(int x,int y,int z,int zo){ u[++t]=x;v[t]=y;c[t]=z;co[t]=zo;nxt[t]=g[x];g[x]=t; u[++t]=y;v[t]=x;c[t]=0;co[t]=-zo;nxt[t]=g[y];g[y]=t;}inline bool spfa(){ int x,i; for(i=1;i<=T;i++)d[i]=-inf,in[i]=0; d[S]=0;in[S]=1;l=r=M>>1;q[l]=S; while(l<=r){ x=q[l++]; if(x==T)continue; for(i=g[x];i;i=nxt[i])if(c[i]&&co[i]+d[x]>d[v[i]]){ d[v[i]]=co[i]+d[x];f[v[i]]=i; if(!in[v[i]]){ in[v[i]]=1; if(d[v[i]]>d[q[l]])q[--l]=v[i];else q[++r]=v[i]; } } in[x]=0; } return d[T]>-inf;}int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]); for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&b[i][j]); for(i=1;i<=n;i++)for(j=1;j<=m;j++){ id[i][j][0]=++T; id[i][j][1]=++T; id[i][j][2]=++T; } T++; for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(!a[i][j]){ ans-=b[i][j]; if((i+j)&1){ cS+=2; add(S,id[i][j][2],2,0); add(id[i][j][2],id[i][j][0],1,0); add(id[i][j][2],id[i][j][0],1,b[i][j]); add(id[i][j][2],id[i][j][1],1,0); add(id[i][j][2],id[i][j][1],1,b[i][j]); if(id[i-1][j][0])add(id[i][j][0],id[i-1][j][0],1,0); if(id[i+1][j][0])add(id[i][j][0],id[i+1][j][0],1,0); if(id[i][j-1][0])add(id[i][j][1],id[i][j-1][1],1,0); if(id[i][j+1][0])add(id[i][j][1],id[i][j+1][1],1,0); }else{ cT+=2; add(id[i][j][2],T,2,0); add(id[i][j][0],id[i][j][2],1,0); add(id[i][j][0],id[i][j][2],1,b[i][j]); add(id[i][j][1],id[i][j][2],1,0); add(id[i][j][1],id[i][j][2],1,b[i][j]); } } if(cS!=cT)return puts("-1"),0; while(spfa()){ for(tmp=inf,i=T;i!=S;i=u[f[i]])if(tmp>c[f[i]])tmp=c[f[i]]; for(ans+=d[i=T]*tmp,flow+=tmp;i!=S;i=u[f[i]])c[f[i]]-=tmp,c[f[i]^1]+=tmp; } if(flow!=cS)return puts("-1"),0; return printf("%d",ans),0;}
BZOJ4261 : 建设游乐场
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。