此帐号已被封,内容无法查看 此帐号的内容被自由微信解封
文章于 2022年1月15日 被检测为删除。
查看原文
被微信屏蔽
其他

最大匹配之网络流解法

正经兔 正经兔 2022-01-15
一看这个标题就知道今天又是快到优化年龄的老正经兔宝宝了。
在二分图,也就是高中数学里说的映射,有一个匹配问题。
匹配
给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配
图中加粗的边是数量为2的匹配。

最大匹配和完全匹配
选择边数最大的子图称为图的最大匹配(maximal matching)。
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。图中所示为一个最大匹配,但不是完全匹配。
现有如下问题:
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:
第2列是否完全匹配很简单:如果左右两边点个数相同、且等于最大匹配数,那就是Y;所以主要还是怎样求最大匹配
有种做法是匈牙利算法,也就是DFS不断寻找匹配,LC上有类似的男女匹配问题求是否能全找到对象,属于hard题。
另一种做法就是把它转化为网络流来做。
前面例子里的第一个:
画成二分图是这样的:
(人眼一看很显然最大匹配就是2,是完全匹配)
为了转化成网络流,添加源点和汇点,分别连接左右两列,然后给所有的边添加方向、并且capacity都设为1:
这样,原图的最大匹配值,就相当于上图中最大流量值,就是2。
求最大流量是好做的,上礼拜推过:网络流算法之最大流量计算
不过这次输入的例子,两列点的编号一样,这是不行的,要变化一下。比如可以把右边的一列变成3、4或者-1、-2。本宝宝选择左边一列为整数1、2,右边一列为字符串"1"、”2“,然后源点汇点分别为0和”0“,比较方便:
所以也就开始画图的过程稍微多两步,其它都和上次一样。python代码如下:
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)
输入样例运行结果正确:

推荐阅

腾讯员工沉迷赌博自杀未遂说明了什么?

网络流算法之最大流量计算

hm事件该怎么看

带权重的区间调度问题(Weighted Interval Scheduling)

今日争论之新中考方案公不公平

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存