ABC274G 社论
题目链接
这道题一开始有一个显然的思路：分别按行和列看这张图，每一行会被障碍物分成几段，每一列也会被障碍物分成几段，放置一个摄像头只能覆盖一段。
开始我是想的贪心，但是交上去发现 WA 了。后来我突然想到，如果将一个空地看成边，“段”看成点，那么实际上是一张二分图。
所以问题就转化成了：在二分图上选一些点，使得每一条边都至少连接着一个被选中的点，要求选的点尽量少。
因为我见识浅薄，只感觉这是一个经典问题，但不知道名字。我在网上查到它叫二分图最小点覆盖，并且等于二分图最大匹配。
艹，怎么又考网络流！没办法，先去把网络流给学了。然后把这道题 A 了。
#include<bits/stdc++.h>
using namespace std;
namespace MF{
constexpr int N=2e5,M=4e5,INF=0x3f3f3f3f,s=1,t=2;
int n,tot=1,dep[N],head[N],nxt[M],to[M],w[M],cur[N];
inline void addArc(int u,int v,int f){
nxt[++tot]=head[u];
to[tot]=v;w[tot]=f;
head[u]=tot;
}
inline void add(int u,int v){
addArc(u,v,1);addArc(v,u,0);
n=max({n,u,v});
}
inline bool bfs(){
for(int i=1;i<=n;i++)cur[i]=head[i],dep[i]=0;
static int q[N],hd,tl;dep[s]=1;q[hd=tl=1]=s;
while(hd<=tl)for(int u=q[hd++],v,i=head[u];i;i=nxt[i]){
v=to[i];if(w[i]>0&&!dep[v]){
dep[v]=dep[u]+1;q[++tl]=v;
if(v==t)return 1;
}
}return 0;
}
int dfs(int u,int flow){
if(u==t||flow<=0)return flow;
int used=0;
for(int i=cur[u],v,f;i;i=nxt[i]){
v=to[i];cur[u]=i;
if(dep[v]==dep[u]+1&&(f=dfs(v,min(w[i],flow-used)))>0){
w[i]-=f;w[i^1]+=f;used+=f;
if(used>=flow)break;
}
}return used;
}
int Dinic(){
int ret=0;
while(bfs())ret+=dfs(s,INF);
return ret;
}
}
constexpr int N=305;
int n,m,t1,t2,tot,b1[N*N],b2[N*N],p[N][N];
char s[N][N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++)if(s[i][j]=='.'){
p[i][j]=++tot;
if(s[i][j-1]=='.')b1[tot]=t1;
else MF::add(1,2+(b1[tot]=++t1));
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++)if(s[i][j]=='.'){
if(s[i-1][j]=='.')b2[p[i][j]]=t2;
else MF::add(2+t1+(b2[p[i][j]]=++t2),2);
}
}
for(int i=1;i<=tot;i++)MF::add(b1[i]+2,b2[i]+t1+2);
cout<<MF::Dinic()<<endl;
return 0;
}