题解 BZOJ 1735 [Usaco2005 jan]Muddy Fields 泥泞的牧场

题解:

  • 不能盖住好地,那么宽为1的木板只能放在行、列连通块里。
  • 所以行、列连通块对应左、右部中的点,泥地对应边。
  • 求二分图最小覆盖就是答案。

二分图最小点覆盖==最大匹配

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
typedef long long ll;
const double eps(1e-10);
int R,C,n;
char s[60][60];
int link[1005];
int cover[1005];
int H[1005],X[1000050],P[1000050],tot;
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
bool find(int x){
for(int i=H[x];i;i=X[i]){
if(cover[P[i]]) continue;
cover[P[i]]=1;
int q=link[P[i]];
link[P[i]]=x;
if(q==-1||find(q)) return 1;
link[P[i]]=q;
}
return 0;
}
int xn,yn;
int a[60][60],b[60][60];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
memset(link,-1,sizeof link);
scanf("%d%d",&R,&C);
for(int i=0;i<R;i++){
scanf("%s",s[i]);
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
if(s[i][j]=='*'){
if(j>0&&s[i][j-1]=='*'){
a[i][j]=a[i][j-1];
}else a[i][j]=++yn;
if(i>0&&s[i-1][j]=='*'){
b[i][j]=b[i-1][j];
}else b[i][j]=++xn;
}
}
}
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
if(s[i][j]=='*'){
add(a[i][j],b[i][j]);
}
}
}
n=yn;
int ans(0);
for(int i=1;i<=n;i++){
memset(cover,0,sizeof cover);
if(find(i)) ans++;
}
printf("%d\n",ans);
return 0;
}

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框