难度: Medium
Submission
运行时间: 96 ms
内存: 18.5 MB
class BipartiteMatching:
def __init__(self, n, m):
self._n = n
self._m = m
self._to = [[] for _ in range(n)]
def add_edge(self, a, b):
self._to[a].append(b)
def solve(self):
n, m, to = self._n, self._m, self._to
prev = [-1] * n
root = [-1] * n
p = [-1] * n
q = [-1] * m
updated = True
while updated:
updated = False
s = []
s_front = 0
for i in range(n):
if p[i] == -1:
root[i] = i
s.append(i)
while s_front < len(s):
v = s[s_front]
s_front += 1
if p[root[v]] != -1:
continue
for u in to[v]:
if q[u] == -1:
while u != -1:
q[u] = v
p[v], u = u, p[v]
v = prev[v]
updated = True
break
u = q[u]
if prev[u] != -1:
continue
prev[u] = v
root[u] = root[v]
s.append(u)
if updated:
for i in range(n):
prev[i] = -1
root[i] = -1
return [(v, p[v]) for v in range(n) if p[v] != -1]
class Solution:
def maximumInvitations(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
bm = BipartiteMatching(m, n)
for i in range(m):
for j in range(n):
if grid[i][j]:
bm.add_edge(i, j)
matching = bm.solve()
return len(matching)
Explain
这道题可以使用匈牙利算法来求解二分图的最大匹配。首先，将给定的网格视为一个二分图，其中每个行和列分别代表二分图的两个部分。如果网格中的某个位置是1，那么就在对应的行和列之间添加一条边。接着，使用匈牙利算法来找出二分图的最大匹配。匈牙利算法的核心思想是通过增广路径来不断地增加匹配的数量。当找不到增广路径时，算法结束，此时的匹配数量就是二分图的最大匹配。
时间复杂度: O((m+n) * E)
空间复杂度: O(E + V)
class BipartiteMatching:
def __init__(self, n, m):
self._n = n # 二分图左侧顶点的数量
self._m = m # 二分图右侧顶点的数量
self._to = [[] for _ in range(n)] # 邻接表
def add_edge(self, a, b):
self._to[a].append(b) # 添加边
def solve(self):
n, m, to = self._n, self._m, self._to
prev = [-1] * n
root = [-1] * n
p = [-1] * n # 左侧顶点的匹配情况
q = [-1] * m # 右侧顶点的匹配情况
updated = True
while updated:
updated = False
s = []
s_front = 0
for i in range(n):
if p[i] == -1:
root[i] = i
s.append(i)
while s_front < len(s):
v = s[s_front]
s_front += 1
if p[root[v]] != -1:
continue
for u in to[v]:
if q[u] == -1:
while u != -1:
q[u] = v
p[v], u = u, p[v]
v = prev[v]
updated = True
break
u = q[u]
if prev[u] != -1:
continue
prev[u] = v
root[u] = root[v]
s.append(u)
if updated:
for i in range(n):
prev[i] = -1
root[i] = -1
return [(v, p[v]) for v in range(n) if p[v] != -1]
class Solution:
def maximumInvitations(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
bm = BipartiteMatching(m, n)
for i in range(m):
for j in range(n):
if grid[i][j]:
bm.add_edge(i, j)
matching = bm.solve()
return len(matching)
Explore
将网格问题转换成二分图可以利用已有的图论算法来求解问题，这种转换能够明确地表达元素间的关系和约束条件。在二分图中，每个顶点只与对立集合中的顶点相连，不存在同集合内的顶点直接连接，这样的特性使得二分图的问题（如求最大匹配）有清晰的算法解决方案。对于网格问题，将行和列分别看作二分图的两部分，可以将网格中元素的相互作用转化为行与列之间的连接关系，从而使用图论中的匹配算法来优化和简化问题求解过程。
在匈牙利算法中，增广路径是指从一个未匹配的左顶点开始，通过交错的匹配和非匹配边，最终到达一个未匹配的右顶点的路径。具体来说，增广路径的标准是：路径的起始点和终点顶点均未被匹配，且路径上的边交替出现在匹配边和非匹配边之间。找到这样的路径后，可以通过反转路径上匹配边和非匹配边的状态来增加匹配的总数，这是算法核心增加匹配数量的方法。
在匈牙利算法中，增广路径的寻找是在算法的主循环中进行的。具体过程如下： 1. 初始化所有左顶点为未匹配状态，遍历每个未匹配的左顶点作为起始点。 2. 使用广度优先搜索（BFS）或深度优先搜索（DFS）从当前未匹配的左顶点出发，探索所有可能的路径。 3. 对于当前顶点的每一个相邻顶点，检查是否未匹配或者是否可以通过递归地寻找该顶点的匹配点的增广路径来释放该顶点，使得当前顶点也变得可匹配。 4. 如果找到从当前左顶点出发的增广路径，则更新路径上的匹配关系，即交换匹配边和非匹配边的状态。 5. 重复此过程，直到无法找到新的增广路径为止。每次找到增广路径后，匹配的数量会增加一个单位，直至算法终止。