[ABC274G] Security Camera 3 做题记录

题意简述

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

$1 \leq H, W \leq 300$ ，时间限制 $2 s$ ，内存限制 $1 G B$ 。

思路

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

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

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

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

根据定理，二分图最大匹配数等于二分图最小覆盖数。由于该二分图点数是，边数也是的，朴素二分图匹配时间复杂度不可接受，使用网络流高效求解，时间复杂度。

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();
}
CPP