[ABC274G] Security Camera 3 做题记录

题意简述

一个 $H\times W$ 的矩形区域，某些格子上会有障碍，你可以在没有障碍的格子上放置任意个摄像头，摄像头可以朝向上下左右四个方向，每个摄像头能监视到的区域是从当前格子开始，向该摄像头的方向延伸直到边界或者障碍物的区域，求至少需要多少个摄像头才能让所有没有障碍的格子都被监视到。

$1\le H,W\le300$，时间限制 $\rm{2s}$，内存限制 $\rm{1GB}$。

思路

首先，我们可以得出一些结论：

• 在一段连续的空地中间放置这个方向的摄像头不会让答案变优。如图 1，在 $1$ 和 $2$ 中间放置摄像头不会让答案变优。于是只需在障碍旁边以及边界旁边放置摄像头。
• 事实上，四个方向中只用在横向和纵向中分别选一个方向设置，剩余两个方向是无需设置摄像头的。如图 1，在 $1$ 号位置放一个方向向右的摄像头和在 $2$ 放置一个方向向左的摄像头的效果是完全一致的，通过这种方式，我们总能把横向和纵向的摄像头统一为两个方向，且选摄像头的本质是在这个方向上选出一段极长的连续空地并覆盖。

问题转化为需要在横向和纵向选择一些极长连续的空地并覆盖，使得每个空地都至少被覆盖一遍。

由于只有两个方向，很容易想到二分图。二分图左边是横向的极长连续段，右边是纵向的极长的连续段。枚举每个空地，将其所属的横向极长连续段与纵向极长连续段连边。每个空地都被覆盖转化为求这个二分图的最小覆盖。

根据 $\rm{K\ddot onig}$ 定理，二分图最大匹配数等于二分图最小覆盖数。由于该二分图点数是 $HW$，边数也是 $HW$ 的，朴素二分图匹配时间复杂度不可接受，使用网络流高效求解，时间复杂度 $O(HW\sqrt{HW})$。

Code

需要预处理出每个空地属于哪个极长连续段。

constexpr int N=305;
char mp[N][N];
struct edge{int to,nxt,w;}e[N*N*8];
int head[N*N*2],cnt=1;
inline void _add(int u,int v,int w){e[++cnt]=(edge){v,head[u],w};head[u]=cnt;}
inline void add(int u,int v,int w){_add(u,v,w);_add(v,u,0);}
int dep[N*N*2],cur[N*N*2],s,t;
inline bool bfs()
{
    memset(dep,-1,sizeof(dep));memcpy(cur,head,sizeof(head));
    dep[s]=0;queue<int>q;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(~dep[v]||!e[i].w)continue;
            dep[v]=dep[u]+1;q.push(v);
        }
    }
    return ~dep[t];
}
inline int dfs(int u,int fin)
{
    if(!fin||u==t)return fin;
    int fout=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w)
        {
            int f=dfs(v,min(fin,e[i].w));
            e[i].w-=f;e[i^1].w+=f;fin-=f;fout+=f;
            if(!fin)break;
        }
    }
    return fout;
}
inline int dinic()
{
    int ans=0;
    while(bfs())ans+=dfs(s,1e9);
    return ans;
}
int prel[N][N],preu[N][N];
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>(mp[i]+1);
    int tot=3;s=1,t=2;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='.'){if(prel[i][j-1])prel[i][j]=prel[i][j-1];else prel[i][j]=++tot,add(s,tot,1);}
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='.'){if(preu[i-1][j])preu[i][j]=preu[i-1][j];else preu[i][j]=++tot,add(tot,t,1);}
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='.')add(prel[i][j],preu[i][j],1);
    cout<<dinic();
}