此帐号已被封,内容无法查看 此帐号的内容被自由微信解封。
文章于 2022年1月15日 被检测为删除。
被微信屏蔽
一看这个标题就知道今天又是快到优化年龄的老正经兔宝宝了。 在二分图,也就是高中数学里说的映射,有一个匹配问题。 匹配 给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
图中加粗的边是数量为2的匹配。
最大匹配和完全匹配 选择边数最大的子图称为图的最大匹配(maximal matching)。
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。图中所示为一个最大匹配,但不是完全匹配。 现有如下问题:
第2列是否完全匹配很简单:如果左右两边点个数相同、且等于最大匹配数,那就是Y;所以主要还是怎样求最大匹配。 有种做法是匈牙利算法,也就是DFS不断寻找匹配,LC上有类似的男女匹配问题求是否能全找到对象,属于hard题。 另一种做法就是把它转化为网络流来做。 前面例子里的第一个: 画成二分图是这样的: (人眼一看很显然最大匹配就是2,是完全匹配) 为了转化成网络流,添加源点和汇点,分别连接左右两列,然后给所有的边添加方向、并且capacity都设为1: 这样,原图的最大匹配值,就相当于上图中最大流量值,就是2。 求最大流量是好做的,上礼拜推过:网络流算法之最大流量计算 不过这次输入的例子,两列点的编号一样,这是不行的,要变化一下。比如可以把右边的一列变成3、4或者-1、-2。本宝宝选择左边一列为整数1、2,右边一列为字符串"1"、”2“,然后源点汇点分别为0和”0“,比较方便: 所以也就开始画图的过程稍微多两步,其它都和上次一样。python代码如下: 输入样例运行结果正确:
其他
最大匹配之网络流解法
图中加粗的边是数量为2的匹配。
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。图中所示为一个最大匹配,但不是完全匹配。
Implement an algorithm to determine the maximum matching in a bipartite graph, and, if that matching is perfect (all nodes are matched). Be efficient and use your max-flow implementation from the previous week. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will be 3 positive integers m, n, and q. Numbers m and n are the number of nodes in node set A and node set B. Number q is the number of edges in the bipartite graph. For each edge, there will be 2 more positive integers z, and j representing an edge between node 1 < i < m in A and node 1 < i < n in B.
A sample input is the following:
The sample input has 3 instances. For each instance, your program should output the size of the maximum matching, followed by a space, followed by an N if the matching is not perfect and a V if the matching is perfect. Each output lineshould be terminated by a newline. The correct output to the sample input would be:
from collections import defaultdict
def readData():
graph=defaultdict(int)
neigh=defaultdict(set) #邻接表
a,b,n=[int(x) for x in input().split()]
for i in range(n):
node1,node2=input().split()
node1=int(node1)
#画边
graph[(node1,node2)]=1
graph[(0,node1)]=1
graph[(node2,"0")]=1
#更新邻接表
neigh[node1].add(node2)
neigh[0].add(node1)
neigh[node2].add("0")
return a,b,graph,neigh
def bfs(s,t,parent):
visited={s}
li=[s]
while li!=[]:
p=li.pop(0)
if p==t:return True
for x in neigh[p]:
if x not in visited:
visited.add(x)
li.append(x)
parent[x]=p
return False
def FordFulkerson(s,t):
maxflow=0
parent = defaultdict(int)
while bfs(s, t,parent):
flow = float("Inf")
v = t
while v != s:
flow = min(flow, graph[(parent[v],v)])
u = parent[v]
graph[(u, v)] -= flow
if graph[(u, v)] == 0: neigh[u].remove(v)
graph[(v, u)] += flow
neigh[v].add(u)
v = u
maxflow += flow
return maxflow
if __name__ == '__main__':
num = int(input())
res=[]
for i in range(num):
a,b,graph,neigh=readData()
match=FordFulkerson(0,"0")
if match==a and match==b:
res.append(str(match)+" Y")
else:
res.append(str(match) + " N")
for x in res:
print (x)
推荐阅读
带权重的区间调度问题(Weighted Interval Scheduling)