Sgu 388. Soap Opera

http://acm.sgu.ru/problem.php?contest=0&problem=388
。。。开始写点题解了。。
题目大意:
给你一个二分图,然后有红色和蓝色两类边,求一个最大子集,
使这个子集不论对于红色边,还是对于蓝色边,都能有完美匹配。。
比如红色边是1-2,3-4,蓝色边是1-4,3-2。。那么1,2,3,4满足条件。。

这个题目初看很不可捉。。仔细想想发现还是可捉的。。关键是说。。在这个结果子集中,每个点都被一条红边和蓝边
连接,那么可以看成红边进入该店,蓝边离开该点。。那么其实就是说。。。。是一个流>_<。。。
那么我们给边一个费用1。。找一个最大费用可行流就可以了。。
算法具体就不说了。。我是用消圈算法的。。。因为有正环所以spfa之类的就要悲剧了。。

P.S.洲妹妹好厉害。。SPOJ已经轻松Rank50了Orz!!!!!!!!!!!!1

2 thoughts on “Sgu 388. Soap Opera

  1. this before but it’s worth metioinnng again: the golf shoe game has changed. Seriously, go down to your local golf store and peruse the shoe section. You’ll likely find a bunch of standard models on the wall, but if you look closely you’ll notice there’s a growing trend within the industry, as golf manufacturers continue to release designs that look more like your standard running or trail shoe than something you’d slip on for your usual Sunday morning round.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>