題目是說給定一個 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