[这是经典问题:-“有M个求职者,N个求职者。每个求职者都有他/她感兴趣的一部分工作。每个职位空缺只能接受一个求职者,并且可以指定一个求职者仅一份工作。找到分配给申请人的工作,以使尽可能多的申请人获得工作。“
我正在使用以下代码和算法来解决问题:https://www.geeksforgeeks.org/maximum-bipartite-matching/
此算法的时间复杂度是多少?
根据this维基百科文章,Ford&Fulkerson的算法的运行时复杂度为O(|E|f)
,其中|E|
是输入边集的基数。请注意,此运行时范围取决于最佳值,并且是伪多项式。