作者chhsiao (bye~)
看板ACMCLUB
标题[讨论] ACM ICPC Taipei site 2005 Problem 9
时间Mon Oct 31 23:19:41 2005
题目是说给定一个 weighted directed graph G,
要求找到一些 vertex-disjoint cycles 覆盖所有的点,
并使这些 cycles 所使用的边的 weight 总和最小.
晚上想到了一个作法, 应该可以用 min cost max flow 来解.
模型的建法是把 G 里面的所有点 v 都拆成两个点 v1 及 v2,
如果在 G 里面有一条边从 u 到 v, 那就从 u1 连一条边到 v2.
接下来对这个新的 graph 求 min cost complete matching.
求出来的 matching 之中的边就是我们要的 cycle edges.
因为如果每个点都有被 matched,
就表示在选到的边里, 每个点的 in degree 和 out degree 都是 1,
因此一定会组成 cycles.
而没有 complete matching 若且唯若 G 没有任何 cycle cover.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.52