二分图匹配问题是一个简单的图论问题

一般来说使用匈牙利算法进行求解

但是由于正在学习网络流

希望通过网络流的方法来解决二分图最大匹配问题

听说Dinic方法求解二分图匹配的效率甚至比普通的匈牙利算法的时间复杂度还要低\( O(n\sqrt{m}) \)

所以就想写一发最大流来AC这个题目

首先先构图,源点为0,汇点为n+m+1

左边的编号从1到n

右边部分的编号从n+1到n+m

然后源点和左边连一条权值为1的边

右边与汇点连一条权值为1的边

然后跑一遍Dinic

网络最大流即为答案

注意这里的点数是n+m+2

边数是2*(n+m+e)

题目:洛谷P3386(模板题)

2019-12-26 20:34 Author: WindCry1

分类: 网络流

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注