链接
http://acm.hdu.edu.cn/showproblem.php?pid=4185
题意
求 $nn$ 的 $01$ 矩阵中覆盖最多的 $12$ 的只包含 $1$ 的块的数量，每个点只能在一个块中。
思路
判断右和下是否能和当前点构成 $1*2$ 的块，能则在两点间连边。
建完图后，易发现这是个二分图，求二分图最大匹配。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=605;
int n,match[N*N];
bool st[N*N];
char s[N][N];
VI g[N*N];
bool dfs(int u) {
for(auto v:g[u]) {
if(st[v]) continue;
st[v]=true;
if(match[v]==-1||dfs(match[v])) {
match[v]=u;
match[u]=v;
return true;
}
}
return false;
}
int main() {
int T;
scanf("%d",&T);
for(int cs=1;cs<=T;cs++) {
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i*n+j].clear();
for(int i=0;i<n;i++) scanf("%s",s[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) {
if(s[i][j]=='.') continue;
if(j+1<n&&s[i][j+1]=='#') {
g[i*n+j].PB(i*n+j+1);
g[i*n+j+1].PB(i*n+j);
}
if(i+1<n&&s[i+1][j]=='#') {
g[i*n+j].PB((i+1)*n+j);
g[(i+1)*n+j].PB(i*n+j);
}
}
int res=0;
for(int i=0;i<n*n;i++) match[i]=-1;
for(int i=0;i<n*n;i++) {
if(match[i]!=-1) continue;
for(int j=0;j<n*n;j++) st[j]=false;
if(dfs(i)) res++;
}
printf("Case %d: %d\n",cs,res);
}
return 0;
}
|