[BZOJ3577]玩手机 - A-Failure的博客

题目

Description

现在有一堆手机放在坐标网格里面（坐标从1开始），坐标(i,j)的格子有s_(i,j)个手机。玩手机当然需要有信号，不过这里的手机与基站与我们不太一样。基站分为两种：发送站和接收站（以下简称为A站和B站）。每个手机必须同时与一个A站和一个B站通信才能工作。每个基站有一个正方形的覆盖范围（平行于网格）。覆盖范围可以用左下角和右上角的坐标表示（范围包括边角）。显然，手机只有在某个基站的范围内才能与这个基站通信。除此之外，每个基站还有最大接入的手机数量限制。求最大同时工作的手机数量。

Input

第一行四个整数R,C,a,b，表示坐标网格的规模是R×C，共有a个A站和b个B站。接下来是一个R×C的矩阵，第i行第j列的数为s_(i,j)。接下来a行，每行5个数w,x1,y1,x2,y2，表示第i个A站最大接入w个手机，覆盖范围为(x1,y1)～(x2,y2)。接下来b行，每行5个数w,x1,y1,x2,y2，含义同上。

Output

一个整数，即最大同时工作的手机数量。

Sample Input

3 3 1 2
1 1 1
1 1 1
1 1 1
100 1 1 3 3
4 1 1 2 2
4 2 2 3 3

Sample Output

数据规模与约定

1≤R,C≤60,0≤a,b≤10,000,0≤s,w≤10,000,1≤x1≤x2≤R,1≤y1≤y2≤C。

题解

很容易想到网络流，$A\rightarrow S\rightarrow B$，但是如果一个$A$与所有范围内的点都连边的肯定会TLEMLE

考虑优化连边，~~很容易~~想到用线段树类似的结构优化！

~~四分树优化会MLE不要问我怎么知道的~~

因为限制范围为正方形，所以可以用二维$ST$表优化了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2e5+5,inf=1e8;
struct p{
	int x,y,dis;
}c[MAX<<2];
int tot,T,n,m,A,B,num=1;
int Log[MAX],h[MAX],d[MAX],H[MAX],qu[MAX];
int st[7][61][61],ts[7][61][61];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add(int x,int y,int dis=inf)
{
	c[++num]=(p){h[x],y,dis},h[x]=num;
	c[++num]=(p){h[y],x,0},h[y]=num;
}
void Init()
{
	for(int i=1;i<7;++i)
	  for(int j=1;j<=n-(1<<i-1)+1;++j)
	    for(int k=1;k<=m-(1<<i-1)+1;++k)
	      {
	      	st[i][j][k]=++tot,ts[i][j][k]=++tot;
	      	add(st[i][j][k],st[i-1][j][k]);
	      	add(st[i][j][k],st[i-1][j+(1<<i-1)][k]);
	      	add(st[i][j][k],st[i-1][j][k+(1<<i-1)]);
	      	add(st[i][j][k],st[i-1][j+(1<<i-1)][k+(1<<i-1)]);
	      	add(ts[i-1][j][k],ts[i][j][k]);
	      	add(ts[i-1][j+(1<<i-1)][k],ts[i][j][k]);
	      	add(ts[i-1][j][k+(1<<i-1)],ts[i][j][k]);
	      	add(ts[i-1][j+(1<<i-1)][k+(1<<i-1)],ts[i][j][k]);
		  }
}
bool bfs()
{
	memset(d,0,sizeof(d));
	int hl=1,tl=d[0]=1;
	while(hl<=tl)
	{
		int tt=qu[hl++];
		for(int i=h[tt];i;i=c[i].x)
		  if(!d[c[i].y]&&c[i].dis)
		  {
		  	d[c[i].y]=d[tt]+1,qu[++tl]=c[i].y;
		  	if(c[i].y==T) return 1;
		  }
	}
	return 0;
}
int dfs(int x=0,int dix=inf)
{
	if(x==T||!dix) return dix;
	int sum=0;
	for(int &i=H[x],dis;i;i=c[i].x)
	  if(d[c[i].y]==d[x]+1&&c[i].dis)
	  {
	  	dis=dfs(c[i].y,min(dix,c[i].dis));
	  	if(dis)
	  	{
	  		sum+=dis,dix-=dis,c[i].dis-=dis,c[i^1].dis+=dis;
	  		if(!dix) break;
		}
	  }
	if(!sum) d[x]=-2;
	return sum;
}
int Dinic()
{
	int tot=0,D;
	while(bfs())
	{
		memcpy(H,h,sizeof(h));
		while(D=dfs()) tot+=D;
	}
	return tot;
}
void change(int xl,int xr,int yl,int yr,int d)
{
	int Logx=Log[xr-xl+1];
	add(d,st[Logx][xl][yl]),add(d,st[Logx][xl][yr-(1<<Logx)+1]),add(d,st[Logx][xr-(1<<Logx)+1][yl]),add(d,st[Logx][xr-(1<<Logx)+1][yr-(1<<Logx)+1]);
}
void _change(int xl,int xr,int yl,int yr,int d)
{
	int Logx=Log[xr-xl+1];
	add(ts[Logx][xl][yl],d),add(ts[Logx][xl][yr-(1<<Logx)+1],d),add(ts[Logx][xr-(1<<Logx)+1][yl],d),add(ts[Logx][xr-(1<<Logx)+1][yr-(1<<Logx)+1],d);
}
int main()
{
	n=read(),m=read(),A=read(),B=read(),Log[0]=-1;
	for(int i=1;i<=max(n,m);++i)
	  Log[i]=Log[i>>1]+1;
	for(int i=1;i<=n;++i)
	  for(int j=1;j<=m;++j)
	    st[0][i][j]=++tot,ts[0][i][j]=++tot,add(st[0][i][j],ts[0][i][j],read());
	Init(),T=++tot;
	for(int i=1,x,xl,xr,yl,yr;i<=A;++i)
	  x=read(),xl=read(),yl=read(),xr=read(),yr=read(),change(xl,xr,yl,yr,++tot),add(0,tot,x);
	for(int i=1,x,xl,xr,yl,yr;i<=B;++i)
	  x=read(),xl=read(),yl=read(),xr=read(),yr=read(),_change(xl,xr,yl,yr,++tot),add(tot,T,x);
	return printf("%d",Dinic()),0;
}

题目