BZOJ3577:玩手机(最大流,二维ST表)

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。

Solution

朴素的网络流应该很简单，直接$r \times c$的每个格子拆点，左边连$a$基站右边连$b$基站，然后$a$基站连源点，$b$基站连汇点就好了。

但是这样的话会边数爆炸，所以可以用二维$ST$表优化连边。具体的可以看$Claris$神仙的博客QwQ

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<queue>

 #define N (300009)

 #define INF (0x7f7f7f7f)

 using namespace std;

 struct Edge{int to,next,flow;}edge[N<<];

 int r,c,a,b,w,x,y,u,v,id_num,val,s,t=;

 int Depth[N],f[][][],g[][][],LOG2[];

 int head[N],num_edge;

 queue<int>q;

 void add(int u,int v,int l)

 {

     edge[++num_edge]=(Edge){v,head[u],l}; head[u]=num_edge;

     edge[++num_edge]=(Edge){u,head[v],}; head[v]=num_edge;

 }

 int DFS(int x,int low,int t)

 {

     if (x==t || !low) return low;

     int f=;

     for (int i=head[x]; i; i=edge[i].next)

         if (Depth[edge[i].to]==Depth[x]+)

         {

             int Min=DFS(edge[i].to,min(low,edge[i].flow),t);

             edge[i].flow-=Min;

             edge[((i-)^)+].flow+=Min;

             f+=Min; low-=Min;

             if (!low) break;

         }

     if (!f) Depth[x]=-;

     return f;

 }

 bool BFS(int s,int t)

 {

     memset(Depth,,sizeof(Depth));

     Depth[s]=;

     q.push(s);

     while (!q.empty())

     {

         int x=q.front(); q.pop();

         for (int i=head[x]; i; i=edge[i].next)

             if (!Depth[edge[i].to] && edge[i].flow)

             {

                 Depth[edge[i].to]=Depth[x]+;

                 q.push(edge[i].to);

             }

     }

     return Depth[t];

 }

 int Dinic(int s,int t)

 {

     int ans=;

     while (BFS(s,t))

         ans+=DFS(s,INF,t);

     return ans;

 }

 int main()

 {

     for (int i=; i<=; ++i) LOG2[i]=LOG2[i>>]+;

     scanf("%d%d%d%d",&r,&c,&a,&b);

     for (int i=; i<=r; ++i)

         for (int j=; j<=c; ++j)

         {

             scanf("%d",&val);

             f[i][j][]=++id_num; g[i][j][]=++id_num;

             add(f[i][j][],g[i][j][],val);

         }

     for(int k=; k<; ++k)

         for(int i=; i<=r; ++i)

             for(int j=; j<=c; ++j)

                 if(i+(<<k)-<=r && j+(<<k)-<=c)

                 {

                     f[i][j][k]=++id_num; g[i][j][k]=++id_num;

                     add(f[i][j][k],f[i][j][k-],INF); add(g[i][j][k-],g[i][j][k],INF);

                     add(f[i][j][k],f[i+(<<k-)][j][k-],INF); add(g[i+(<<k-)][j][k-],g[i][j][k],INF);

                     add(f[i][j][k],f[i][j+(<<k-)][k-],INF); add(g[i][j+(<<k-)][k-],g[i][j][k],INF);

                     add(f[i][j][k],f[i+(<<k-)][j+(<<k-)][k-],INF); add(g[i+(<<k-)][j+(<<k-)][k-],g[i][j][k],INF);

                 }

     for (int i=; i<=a; ++i)

     {

         scanf("%d%d%d%d%d",&w,&x,&y,&u,&v);

         add(s,++id_num,w);

         int k=LOG2[u-x+];

         add(id_num,f[x][y][k],INF);

         add(id_num,f[x][v-(<<k)+][k],INF);

         add(id_num,f[u-(<<k)+][y][k],INF);

         add(id_num,f[u-(<<k)+][v-(<<k)+][k],INF);

     }

     for (int i=; i<=b; ++i)

     {

         scanf("%d%d%d%d%d",&w,&x,&y,&u,&v);

         add(++id_num,t,w);

         int k=LOG2[u-x+];

         add(g[x][y][k],id_num,INF);

         add(g[x][v-(<<k)+][k],id_num,INF);

         add(g[u-(<<k)+][y][k],id_num,INF);

         add(g[u-(<<k)+][v-(<<k)+][k],id_num,INF);

     }

     printf("%d\n",Dinic(s,t));

 }

秒客网