BZOJ3577 : 玩手机

很明显网络流。

S到每个发射站连边，容量为该站限制

每个接收站到T连边，容量为该站限制

矩阵每个点拆成两个点i和i',i向i'连边，容量为该位置手机数

每个发射站向该正方形内所有点i连边，容量为无穷大

每个接收站向该正方形内所有点i'连边，容量为无穷大

求最大流即可。

但是这样的话，TLE+MLE（内存限制只有32M）

可以发现每个站点连出去的都是一个正方形，所以有种神奇的优化方法

跟A+B Problem类似，那道题是每次连的一定是个区间，所以建立线段树后用一个点代表一个区间，父节点向儿子节点连边

这题也类似，不过因为连得容量都是无穷大，所以[1,10]这个区间即使被拆成[1,8][2,10]都不影响答案，

所以可以用二维ST表来优化，

fs[i][j][k]表示左上角为(i,j)，边长为$2^k$的正方形所代表的点的ID

ft[i][j][k]表示左上角为(i,j)，边长为$2^k$的正方形所代表的点拆点后另一个点的ID

很明显fs[i][j][0]要向ft[i][j][0]连边，容量为(i,j)处手机数量

然后是预处理

fs[i][j][k]

向

fs[i][j][k-1]

fs[i+2^(k-1)-1][j][k-1]

fs[i][j+2^(k-1)-1][k-1]

fs[i+2^(k-1)-1][j+2^(k-1)-1][k-1]

连边，容量为无穷大

ft[i][j][k-1]

ft[i+2^(k-1)-1][j][k-1]

ft[i][j+2^(k-1)-1][k-1]

ft[i+2^(k-1)-1][j+2^(k-1)-1][k-1]

向

ft[i][j][k]

连边，容量为无穷大

对于每个发射站，

向

fs[x1][y1][log(边长)]

fs[x1][y2-2^log(边长)+1][log(边长)]

fs[x2-2^log(边长)+1][y1][log(边长)]

fs[x2-2^log(边长)+1][y2-2^log(边长)+1][log(边长)]

连边，容量为无穷大

对于每个接收站，

ft[x1][y1][log(边长)]

ft[x1][y2-2^log(边长)+1][log(边长)]

ft[x2-2^log(边长)+1][y1][log(边长)]

ft[x2-2^log(边长)+1][y2-2^log(边长)+1][log(边长)]

向它连边，容量为无穷大

这样点数是$n^2\log n+a+b$，边数是$n^2\log n+a+b$，就可以过了

#include<cstdio>

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

const int N=56010,inf=~0U>>2;

int n,S,T,h[N],gap[N],maxflow;

struct edge{int t,f;edge *nxt,*pair;}*g[N],*d[N];

int r,c,a,b,x1,x2,y1,y2,w;

int i,j,k,fs[62][62][6],ft[62][62][6],pow[8],log[62];

inline int min(int a,int b){return a<b?a:b;}

inline void add(int s,int t,int f){

  edge *p=new(edge);p->t=t;p->f=f;p->nxt=g[s];g[s]=p;

  p=new(edge);p->t=s;p->f=0;p->nxt=g[t];

  g[t]=p;g[s]->pair=g[t];g[t]->pair=g[s];

}

int sap(int v,int flow){

  if(v==T)return flow;

  int rec=0;

  for(edge *p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){

    int ret=sap(p->t,min(flow-rec,p->f));

    p->f-=ret;p->pair->f+=ret;d[v]=p;

    if((rec+=ret)==flow)return flow;

  }

  d[v]=g[v];

  if(!(--gap[h[v]]))h[S]=T;

  gap[++h[v]]++;

  return rec;

}

int main(){

  for(pow[0]=i=1;i<8;i++)pow[i]=pow[i-1]<<1;

  for(i=1;i<62;i++)for(j=i;j>1;j>>=1,log[i]++);

  read(r);read(c);read(a);read(b);

  for(i=1;i<=r;i++)for(j=1;j<=c;j++){

    fs[i][j][0]=++n,ft[i][j][0]=++n;

    read(k);

    add(fs[i][j][0],ft[i][j][0],k);

  }

  for(k=1;k<6;k++)for(i=1;i<=r;i++)for(j=1;j<=c;j++)if(i+pow[k]-1<=r&&j+pow[k]-1<=c){

    fs[i][j][k]=++n,ft[i][j][k]=++n;

    add(fs[i][j][k],fs[i][j][k-1],inf),add(ft[i][j][k-1],ft[i][j][k],inf);

    add(fs[i][j][k],fs[i+pow[k-1]][j][k-1],inf),add(ft[i+pow[k-1]][j][k-1],ft[i][j][k],inf);

    add(fs[i][j][k],fs[i][j+pow[k-1]][k-1],inf),add(ft[i][j+pow[k-1]][k-1],ft[i][j][k],inf);

    add(fs[i][j][k],fs[i+pow[k-1]][j+pow[k-1]][k-1],inf),add(ft[i+pow[k-1]][j+pow[k-1]][k-1],ft[i][j][k],inf);

  }

  S=n+a+b+1;T=S+1;

  while(a--){

    read(w),read(x1),read(y1),read(x2),read(y2);

    add(S,i=++n,w);

    k=log[j=x2-x1+1];

    add(i,fs[x1][y1][k],inf);

    add(i,fs[x1][y2-pow[k]+1][k],inf);

    add(i,fs[x2-pow[k]+1][y1][k],inf);

    add(i,fs[x2-pow[k]+1][y2-pow[k]+1][k],inf);

  }

  while(b--){

    read(w),read(x1),read(y1),read(x2),read(y2);

    add(i=++n,T,w);

    k=log[j=x2-x1+1];

    add(ft[x1][y1][k],i,inf);

    add(ft[x1][y2-pow[k]+1][k],i,inf);

    add(ft[x2-pow[k]+1][y1][k],i,inf);

    add(ft[x2-pow[k]+1][y2-pow[k]+1][k],i,inf);

  }

  gap[0]=T;

  for(i=0;i++<T;)d[i]=g[i];

  while(h[S]<T)maxflow+=sap(S,inf);

  printf("%d",maxflow);

  return 0;

}

巴特西

BZOJ3577 : 玩手机

最新文章

热门文章