与相关顶点成本相关的二分选择
我想我正在寻找一种可以在二分图中找到“最小”“选择”的算法。 每个顶点都有相关的（整数）成本来选择它。 我只能找到最小化所选集合中顶点数量的算法，而不是成本。 我以前认为我需要一个“匹配”，但实际上我只需要覆盖每条边的顶点子集......
我不认为一个贪婪的解决方案可以工作。 假设我们的集合是A，B：
顶点1,2,3在A中并且具有成本1.顶点4在B中并且具有成本2。
解决方案是去除最昂贵的顶点，4.基于成本选择的贪婪解决方案将失败。 同样，如果B的成本为10，我们就不能贪婪地选择最连接的顶点。
我想到了一个不同的措词：“给定一个二部图，其中每个顶点都有一个相关的成本，找到一个最小代价顶点的子集，使得每个边都入射到您选择的子集中的至少一个顶点。
Primal LP：
min sum_v c_v x_v
s.t.
forall e=vw. x_v + x_w >= 1
forall v. x_v >= 0
双LP：
max sum_e y_e
s.t.
forall v. sum_{e=vw} y_e <= c_v
forall e. y_e >= 0
找到最小切割，其中边是从A到B的具有无限容量的弧，A中的顶点是源，B中的顶点是汇，所有顶点的容量等于其成本。 （等价地，使用弧来创建一个超级源，并使用来自B的弧创建一个超级源。）
以切入点的“汇”侧和“源”侧的B切。 每一条边vw都被覆盖，因为如果v和w都不属于封面，那么vw就是残差。
我想给JenőEgerváry一些提示。
链接地址: http://www.djcxy.com/p/37311.html