Maximal Cliques on Circular-arc Graph
合肥2008現場賽, 2009網賽 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大牛想出二分圖匹配的做法:
固定某個區間Li肯定選中, 則剩下的區間里, 可能被選擇的只有與Li有交集的那些.
(*)將那些區間分兩類: 與Li的左邊界交的, 與Li的右邊界交的.
易知與Li兩邊界都交的是肯定可以選的, 不會產生不合要求的局面.
不合要求的情況只可能是, 某個一類區間和某個二類區間沒有交, 卻同時選了它們.
所以二分圖建圖方法為, 若某個一類區間和某個二類區間沒有交, 則連一條邊.
二分圖的頂點數+1-最大匹配數即為Li對應的最優解.
枚舉每個Li.
理論時間復雜度相當高, O(n)*O(匹配), 實現上可以加入排序, 最優解剪枝等方案.
ps. (*)非常巧妙的想法! 非常藝術!
posted on 2009-09-07 13:23
wolf5x 閱讀(318)
評論(2) 編輯 收藏 引用 所屬分類:
acm_icpc 、
algorithm