京东笔试 考场安排 题解思考 （二分图最小顶点覆盖问题）
看到大家讨论比较热烈，就自己做了一下。
原题大意：
n代表了男生和女生的人数 其中男生序号[1, n] 女生 [n+1, 2n]
m代表了接下来输入的行数
每行输入两个数 第一个代表了男生的序号 第二个代表了女生的序号 表示该男生和女生之间会在考试的时候作弊
我们最少把多少人踢出考场才能保证考场上的人不存在作弊行为 输出这个最小值 并且把踢出的人的序号按照升序排序输出
--------------------------
实际上是二分图最小顶点覆盖问题，主要用到了匈牙利算法、Konig算法，不了解的可以去查一下。
不是考试做的，所以不太好测是不是AC，欢迎讨论👏
另附 最优打印策略（大小写切换）和合唱团分组问题的题解：https://www.nowcoder.com/discuss/232706
P.S. 贪心删除得到的不一定是正确结果，比如下面代码中的样例就是一个反例。
"""
Bipartite graph problem
minimum vertex cover == maximum matching (Konig algorithm)
find maximum matching (Hungarian algorithm)
"""
class BiGraph(object):
def __init__(self, vx, vy, edges):
# vx, vy := the two vertex sets of the bipartite graph
# edges := edge set
self.vx = vx
self.vy = vy
self.edges = edges
def isConnect(self, u, v):
return (v, u) in self.edges or (u, v) in self.edges
def maxMatching(self):
# Hungarian algorithm
# init match set M
res = 0
Mx = {}
My = {}
for v in self.vx:
if v not in Mx:
res += self.augmentPath(Mx, My, v, set())
return res, Mx, My
def augmentPath(self, Mx, My, v, visited):
for u in self.vy:
if self.isConnect(u, v) and u not in visited:
visited.add(u)
if u not in My or self.augmentPath(Mx, My, My[u], visited):
Mx[v] = u
My[u] = v
return True
return False
def minVertexCover(self, Mx, My):
# Konig algorithm
minCover = self.vx
# init non matched vx
stack = [v for v in self.vx if v not in Mx]
visited = set()
while stack:
v = stack.pop()
visited.add(v)
if v in self.vx:
minCover.remove(v)
for u in self.vy:
if self.isConnect(u, v) and u not in visited:
visited.add(u)
minCover.add(u)
if My[u] not in visited:
stack.append(My[u])
return minCover
if __name__ == '__main__':
boys = {1, 2, 3, 4}
girls = {5, 6, 7}
edges = {(1, 5), (2, 5), (2, 6), (2, 7), (3, 6), (4, 7)}
graph = BiGraph(boys, girls, edges)
res, Mx, My = graph.maxMatching()
minCover = graph.minVertexCover(Mx, My)
remove_list = sorted(list(minCover))
print(res, remove_list)
查看8道真题和解析
