用最大流解决二分图最大匹配 Bipartite Matching
用最大流解决二分图最大匹配 Bipartite Matching
·
有A B C三个老师,D E F三门课,A能教E, B能教D和F,C能教D和E。要求每个老师只能教一门课,求分配方案。
这是一个典型的二分图最大匹配问题,二分图是只graph的顶点可以分为两部分,每部分内部顶点直接无连接,每一条边都跨越两部分。
解决方法,在图的左边增加一个顶点s,然后连接左边的所有顶点,在图的右边添加一个顶点t从右边所有顶点到t建立连接。这样就形成了一个流网络,每条边的容量都设为1。
求解最大流之后得到新的图。关于流网络和最大流的求法可以看我最大流的文章。
s和t点去掉,把流量为0的边去掉,剩下的就是我们要求的结果。
有编程基础的根据以上算法思想就可以写出代码,需要提高编程基础的可以找我。
更多推荐
已为社区贡献1条内容
所有评论(0)