二部图最大化最小权重匹配
时间: 2023-07-05 17:19:36 浏览: 77
二部图最大化最小权重匹配问题可以使用二分答案和网络流算法来求解,具体如下:
1. 将二分图拆成左右两侧的顶点集合 $X,Y$,并且对于每个顶点 $u \in X$,从源点 $S$ 向 $u$ 连一条容量为 $1$,费用为 $0$ 的边;对于每个顶点 $v \in Y$,从 $v$ 向汇点 $T$ 连一条容量为 $1$,费用为 $0$ 的边。
2. 对于每一条左侧到右侧的边 $(u,v)$,从 $u$ 向 $v$ 连一条容量为 $1$,费用为该边的权重 $w(u,v)$ 的边。
3. 对于每一条右侧到左侧的边 $(v,u)$,从 $v$ 向 $u$ 连一条容量为 $1$,费用为该边的权重 $w(v,u)$ 的边。
4. 对费用进行二分,假设当前的费用为 $mid$,则将所有费用小于等于 $mid$ 的边的容量设置为 $1$,其余边的容量设置为 $0$。
5. 在新构造的网络中,计算源点 $S$ 到汇点 $T$ 的最小费用最大流,如果最小费用最大流的流量等于左侧顶点的个数,则说明存在一种费用小于等于 $mid$ 的匹配方案,否则不存在。
6. 根据二分答案的思想,不断调整二分的上下界,直到最终找到最小的费用 $ans$,使得存在一种费用小于等于 $ans$ 的匹配方案。
二分答案的时间复杂度为 $O(\log w)$,其中 $w$ 表示边权的上界;网络流算法的时间复杂度为 $O(m^2n)$,其中 $n$ 表示顶点数,$m$ 表示边数。如果使用最大流算法的优化算法,时间复杂度可以优化到 $O(mn\log(w))$,其中 $w$ 表示边权的上界。因此,总的时间复杂度为 $O(\log w \cdot m^2n)$ 或者 $O(\log w \cdot mn\log(w))$。