AcWing 377. 泥泞的区域
原题链接
中等
作者:
追着你行走
,
2021-01-16 00:10:31
,
所有人可见
,
阅读 842
分析:
每块泥地(I,j)要么被行的一块盖住,要么被j列的一块木块盖住,二者至少选一,满足最小覆盖的2要素条件。
木板只能放在行或列连续的泥地上,称之为行泥地块或列泥地块,且分别作为左部与右部节点。
对于每个是泥地的位置(I,j),进行此行泥地块与此列泥地块连边即可,然后运行最大匹配即可。
细节在注释中有写
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Node{ int ver,next;}edge[maxn] ;
char ar[110][110];
int n,m,tot,head[maxn],cnt1=1,cnt2=1,
a[110][110],b[110][110],match[maxn],vis[maxn];
void add(int u,int v) {
edge[++tot].ver=v; edge[tot].next=head[u]; head[u]=tot;
}
bool dfs(int x) { //运行匈牙利算法
for(int i=head[x],y;i;i=edge[i].next) {
if(!vis[y=edge[i].ver]) {
vis[y]=1;
if(!match[y]||dfs(match[y])) {
match[y]=x; return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>ar[i][j];
for(int i=1;i<=n;i++) { //行块号
for(int j=1;j<=m;j++) {
if(ar[i][j]=='*') a[i][j]=cnt1 ;
else cnt1++ ;
} cnt1++;
}
for(int j=1;j<=m;j++) { //列块号
for(int i=1;i<=n;i++) {
if(ar[i][j]=='*') b[i][j]=cnt2 ;
else cnt2++ ;
} cnt2++;
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) { //行号 、列号
if(ar[i][j]=='*') add(a[i][j],b[i][j]); //连边
}
}
int ans=0;
for (int i=1;i<=cnt1;i++) { //行号
memset(vis,0,sizeof(vis) ); //最大匹配边
if(dfs(i)) ans++;
}
cout<<ans<<endl;
return 0;
}
tql
cnt1和cnt2加多了无所谓是吧