Zth's Blog

记录学习路上的点滴

0%

二分图匹配

发表于 更新于 分类于

题目链接

题目大意

在一张$n \times n$的网格图上， 有一些网格禁止触及， 求这张图上能放置$1 \times 2$的棋子的最大数量(棋子间不允许有重叠部分)

题解

《算法竞赛进阶指南》

二分图匹配的模型有两个要素：

1.节点能分成独立的两个集合， 每个集合内部有 0 条边。

2.每个节点只能与 1 条匹配边相连。

我们把它简称为0要素和1要素。

本题中的0元素：将棋盘黑白染色， 则相同颜色的格子之间没有边， 每个格子只有可能与其上下左右的至多四个不同颜色的格子建边。

本题中的1元素：棋子的大小为$1 \times 2$， 恰好覆盖相邻的两个格子， 即每个格子最多和 1 个另一个不同颜色的格子连一条边。

建好图后使用匈牙利算法跑一遍二分图最大匹配就好了

AC代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <cstring>

int n, m;
int match[10004], vis[10004];
int map[102][102], col[102][102], num[102][102];
int head[10004], tot;
struct Edge
{
    int from, to, next;
} edge[20004];
int ans;

void Addedge(int u, int v)
{
    edge[++ tot] = (Edge) {u, v, head[u]};
    
    head[u] = tot;
}

void Build()
{
    for(int i = 1; i <= n; i ++) col[1][i] = col[1][i - 1] ^ 1;
    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            col[i][j] = col[i - 1][j] ^ 1;
    
    int c = col[1][1];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            num[i][j] = (i - 1) * n + j;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(col[i][j] == c && map[i][j] == 0)
            {
                if(j + 1 <= n && map[i][j + 1] == 0) Addedge(num[i][j], num[i][j + 1]);
                if(i + 1 <= n && map[i + 1][j] == 0) Addedge(num[i][j], num[i + 1][j]);
                if(j - 1 >= 1 && map[i][j - 1] == 0) Addedge(num[i][j], num[i][j - 1]);
                if(i - 1 >= 1 && map[i - 1][j] == 0) Addedge(num[i][j], num[i - 1][j]);
            }
}

bool Dfs(int u)
{
    for(int i = head[u]; i; i  = edge[i].next)
    {
        int v = edge[i].to;
        
        if(! vis[v])
        {
            vis[v] = true;
            
            if(!match[v] || Dfs(match[v]))
            {
                match[v] = u;
                
                return true;
            }
        }
    }
    
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        
        scanf("%d%d", &x, &y);
        
        map[x][y] = 1;
    }
    
    Build();
    
    for(int i = 1; i <= n * n; i ++)
    {
        memset(vis, 0, sizeof(vis));
        
        if(Dfs(i)) ans ++;
    }
    
    printf("%d\n", ans);
    
    return 0;
}