题解：P16148 [ICPC 2017 NAIPC] Apple Market

· · 题解

题意简述

有 n\times m 家商店，每家商店有给定的苹果库存。每位顾客只能从给定子矩形内购买苹果，且购买量不超过其预算。求所有顾客购买量之和的最大值。

解题思路

先建立最大流模型。源点向每位顾客连容量为其预算的边。顾客向能访问的商店连容量为无穷的边，每家商店向汇点连容量为其库存的边。每个单位流量对应出售一个苹果，因此最大流就是答案。

直接连接顾客与商店会产生 O(knm) 条边，需要压缩矩形连边。

对每组 p,q，为网格中每个高 2^p、宽 2^q 的子矩形建立节点。若 p>0，从该节点向上下两个高 2^{p-1} 的子矩形连边。若 p=0,q>0，则向左右两个宽 2^{q-1} 的子矩形连边。所有边的容量均为无穷。最后，将每个 1\times1 节点连向汇点，容量为对应商店的库存。

按矩形大小归纳，每个矩形节点都能将流量送到其内部的所有商店。它不能到达矩形外的商店。拆分出的两个子矩形都在原矩形内，且二者的并等于原矩形。故不会遗漏或引入商店。

设顾客矩形的高为 h，取 p=\lfloor\log_2h\rfloor。长度为 2^p 的行前缀和行后缀都包含于该矩形。又有 h<2^{p+1}，所以二者的并覆盖全部行。列方向同理。两组行区间和两组列区间取笛卡尔积，至多得到 4 个二次幂边长的矩形。这些矩形的并恰好是顾客能访问的区域。

将顾客节点连向这至多 4 个矩形节点。压缩图中的路径不会到达访问区域外的商店；区域内的每家商店又至少属于其中一个矩形，故一定可以到达。压缩前后的顾客–商店可达关系完全相同，两个网络的最大流也相同。

二次幂矩形节点与内部边的数量均为 O(nm\log n\log m)，完整网络有 V=O(nm\log n\log m+k) 个节点和 E=O(nm\log n\log m+k) 条边。最大流使用 Dinic，最坏时间复杂度为 O(V^2E)，空间复杂度为 O(V+E)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=55;
const int L=6;
const int V=159056;
const int E=1231201;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct Edge
{
    int v,nxt;
    ll w;
}e[E];
int id[L][L][N][N],pw[L],lg[N];
int hd[V],cur[V],dep[V],que[V],cnt;
ll a[N][N];
void add(int u,int v,ll w)
{
    e[cnt]={v,hd[u],w};
    hd[u]=cnt++;
    e[cnt]={u,hd[v],0};
    hd[v]=cnt++;
}
bool bfs(int s,int t)
{
    fill(dep,dep+V,-1);
    int l=0,r=0;
    que[r++]=s;
    dep[s]=0;
    while(l<r)
    {
        int u=que[l++];
        for(int i=hd[u];i!=-1;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                que[r++]=v;
            }
        }
    }
    return dep[t]!=-1;
}
ll dfs(int u,int t,ll f)
{
    if(u==t)return f;
    ll res=0;
    for(int &i=cur[u];i!=-1&&res<f;i=e[i].nxt)
    {
        int v=e[i].v;
        if(!e[i].w||dep[v]!=dep[u]+1)continue;
        ll d=dfs(v,t,min(f-res,e[i].w));
        if(!d)continue;
        e[i].w-=d;
        e[i^1].w+=d;
        res+=d;
    }
    if(!res)dep[u]=-1;
    return res;
}
ll dinic(int s,int t)
{
    ll ans=0;
    while(bfs(s,t))
    {
        copy(hd,hd+V,cur);
        ans+=dfs(s,t,inf);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
    pw[0]=1;
    for(int i=1;i<L;i++)pw[i]=pw[i-1]*2;
    for(int i=2;i<N;i++)lg[i]=lg[i/2]+1;
    int tot=0;
    for(int i=0;i<=lg[n];i++)
    {
        for(int j=0;j<=lg[m];j++)
        {
            int w=m-pw[j]+1,c=(n-pw[i]+1)*w;
            for(int k=0;k<c;k++)id[i][j][k/w+1][k%w+1]=tot++;
        }
    }
    memset(hd,-1,sizeof hd);
    int s=tot+q;
    for(int i=0;i<q;i++)
    {
        int x1,x2,y1,y2;
        ll x;
        cin>>x1>>x2>>y1>>y2>>x;
        int p=lg[x2-x1+1],r=lg[y2-y1+1];
        int rx[2]={x1,x2-pw[p]+1},cy[2]={y1,y2-pw[r]+1};
        int u=tot+i;
        add(s,u,x);
        for(int j=0;j<2;j++)
        {
            if(j&&rx[j]==rx[0])continue;
            add(u,id[p][r][rx[j]][cy[0]],inf);
            if(cy[1]!=cy[0])add(u,id[p][r][rx[j]][cy[1]],inf);
        }
    }
    for(int i=0;i<=lg[n];i++)
    {
        for(int j=0;j<=lg[m];j++)
        {
            if(!i&&!j)continue;
            int w=m-pw[j]+1,c=(n-pw[i]+1)*w;
            for(int k=0;k<c;k++)
            {
                int x=k/w+1,y=k%w+1,u=id[i][j][x][y];
                if(i)
                {
                    add(u,id[i-1][j][x][y],inf);
                    add(u,id[i-1][j][x+pw[i-1]][y],inf);
                }
                else if(j)
                {
                    add(u,id[i][j-1][x][y],inf);
                    add(u,id[i][j-1][x][y+pw[j-1]],inf);
                }
            }
        }
    }
    int t=s+1;
    for(int i=0;i<n*m;i++)add(id[0][0][i/m+1][i%m+1],t,a[i/m+1][i%m+1]);
    cout<<dinic(s,t)<<'\n';
    return 0;
}