NC 51272. 棋盘覆盖

发表于 分类于

链接

https://ac.nowcoder.com/acm/problem/51272

题意

$nn$ 的棋盘上，有m个点被删除了，求棋盘能被多少个$12$ 的多米诺骨牌进行掩盖

思路

每个点只能被一个骨牌覆盖，所以每个点只能和一个点匹配

对于每个点，判断其相邻的点是否合法，合法则连边，表示可以和其匹配

建完图跑二分图最大匹配

代码

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
#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;
//head
const int N=101;
const int DIR[4][2]={0,-1,0,1,-1,0,1,0};
int n,m,match[N*N];
bool st[N][N],vis[N*N];
VI g[N*N];
bool dfs(int u) {
    for(auto v:g[u]) {
        if(vis[v]) continue;
        vis[v]=true;
        if(match[v]==-1||dfs(match[v])) {
            match[u]=v;
            match[v]=u;
            return true;
        }
    }
    return false;
}
bool valid(int x,int y) {
    if(x>=0&&x<n&&y>=0&&y<n&&!st[x][y]) return true;
    return false;
}
int main() {
    //freopen("D:/Sublime Text 3/in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        x--,y--;
        st[x][y]=true;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<4;k++) {
                int tx=i+DIR[k][0],ty=j+DIR[k][1];
                if(valid(tx,ty)) g[i*n+j].PB(tx*n+ty);
            }
    int res=0;
    for(int i=0;i<n*n;i++) match[i]=-1;
    for(int i=0;i<n*n;i++) {
        if(st[i/n][i%n]||match[i]!=-1) continue;
        for(int j=0;j<n*n;j++) vis[j]=false;
        if(dfs(i)) res++;
    }
    printf("%d\n",res);
    return 0;
}