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;

}