hdu 1853 Cyclic Tour (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 1853 题目链接

题意:一个带权有向图,要求找出若干的环,满足每个点恰好在一个环里,并且环的权值和最小……问最小权值和。

思路:没有思路,不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点

如果有一条边i->j,那么就连一条i->j’的边。

正确性:

对于满足条件的环,每个点的入度和出度均为1,我们可以把每个点拆成入点和出点,那么也就是说一个入点对应一个出点,反之亦然,那么这个问题就变成了一个二分图匹配问题,

 

然后这道题有重边,2A.

又一次体会到了拆点的神奇。。。这个大概算是需要慢慢积累的技巧吧。。像辅助线一样的。。。

还有体会到了环的模型竟然也可以转化成二分图匹配,真是厉害==

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz