posts - 43,  comments - 9,  trackbacks - 0
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 阅读(309) 评论(2)  编辑 收藏 引用 所属分类: acm_icpcalgorithm

FeedBack:
# re: Guarders: Maximal Cliques on Circular-arc Graph
2009-09-08 09:41 | yyz_max@163.com
有实现代码吗?  回复  更多评论
  
# re: Guarders: Maximal Cliques on Circular-arc Graph
2009-09-08 09:43 | yyz_max@163.com
能不能发我邮箱一个啊?
yyz_max@163.com  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜