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

题目大意

给\(n\)个阴属性的珠子，和\(n\)个阳属性的珠子阴阳相邻组成一串项链，同时如果第\(i\)个阴珠子和第\(j\)个阳珠子相邻则会劣化，求最少有多少个阴属性的珠子会劣化。

思路及做法

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

注意因为是个环，所以只需要枚举\(n - 1\)个珠子的排列方式。（因为这个TLE了两发……）

AC-Code (C++)

Time 608MS, Memory 1580K

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