二分图最小点权覆盖的裸题。

解法：

拆点，把一个点拆成入点（关联所有入边）和出点（关联所有有出边），这样将所有入点和出点分置两侧，就可以得到一个二分图。

根据题意，即是求该二分图的最小点权覆盖。

下图是转化为网络流的构图（左为出点）

最小点权覆盖构图

(more…)