摘要
Title: 372. 棋盘覆盖
Tag: 二分图、匈牙利算法
Memory Limit: 64 MB
Time Limit: 1000 ms

372. 棋盘覆盖

题意

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
思路

放一个长度为 2、宽度为 1 的骨牌，相当于两个相邻的点相连，那么我们就可以枚举所有x+y为奇数的点（它的四周一定是偶数点）连四条边，进行二分图最大匹配即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-05 12:00:27
FilePath: \ACM\Acwing\372.py
LastEditTime: 2022-03-05 12:02:13
'''
N = 11000
g = [[] for _ in range(N)]
gg = [0] * N
st, match = [0] * N, [0] * N


def find(u):
    for v in g[u]:
        if st[v] == 0:
            st[v] = 1
            if match[v] == 0 or find(match[v]):
                match[v] = u
                return True
    return False


n, t = map(int, input().split())
for i in range(t):
    x, y = map(int, input().split())
    gg[x * n + y] = 1

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if gg[i * n + j] and (i + j) % 2 == 0:  #偶数的不要
            continue
        for id in range(4):
            x = i + dx[id]
            y = j + dy[id]
            if x >= 1 and x <= n and y >= 1 and y <= n and gg[x * n + y] == 0:
                g[i * n + j].append(x * n + y)

res = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if (i + j) & 1 and gg[i * n + j] == 0:
            st = [0] * N
            if find(i * n + j):
                res += 1
print(res)

372. 棋盘覆盖

题意

思路

代码