HDU 5727 Necklace

Posted on By 二价氢

http://acm.hdu.edu.cn/showproblem.php?pid=5727

题目大意

个阴属性的珠子,和个阳属性的珠子阴阳相邻组成一串项链,同时如果第个阴珠子和第个阳珠子相邻则会劣化,求最少有多少个阴属性的珠子会劣化。

思路及做法

的范围很小,所以可以考虑暴力,暴力的话,就是枚举个阴珠子的排列,然后看能塞进多少个阳珠子使得不劣化,这显然是个二分图最大匹配问题,用匈牙利算法跑一下就好了。

注意因为是个环,所以只需要枚举个珠子的排列方式。(因为这个TLE了两发……)

AC-Code (C++)

Time 608MS, Memory 1580K

https://github.com/erjiaqing/my_solutions/blob/master/hdu/5727.cpp