Maximal Cliques on Circular-arc Graph
合肥2008現(xiàn)場賽, 2009網(wǎng)賽 Guarders
In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. --wiki

uestc_floyd的做法是搜+剪枝.

zzh@bupt大牛想出二分圖匹配的做法:
固定某個(gè)區(qū)間Li肯定選中, 則剩下的區(qū)間里, 可能被選擇的只有與Li有交集的那些.
(*)將那些區(qū)間分兩類: 與Li的左邊界交的, 與Li的右邊界交的.
易知與Li兩邊界都交的是肯定可以選的, 不會產(chǎn)生不合要求的局面.
不合要求的情況只可能是, 某個(gè)一類區(qū)間和某個(gè)二類區(qū)間沒有交, 卻同時(shí)選了它們.
所以二分圖建圖方法為, 若某個(gè)一類區(qū)間和某個(gè)二類區(qū)間沒有交, 則連一條邊.
二分圖的頂點(diǎn)數(shù)+1-最大匹配數(shù)即為Li對應(yīng)的最優(yōu)解.
枚舉每個(gè)Li.
理論時(shí)間復(fù)雜度相當(dāng)高, O(n)*O(匹配), 實(shí)現(xiàn)上可以加入排序, 最優(yōu)解剪枝等方案.

ps. (*)非常巧妙的想法! 非常藝術(shù)!