首页 > 其他 > 详细

hdu6080(最小环)

时间:2017-08-14 19:32:16      阅读:202      评论:0      收藏:0      [点我收藏+]

题目

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

分析

  很妙的思路,将里面的点集当作A,将外面的点集当作B

  然后O(n^2)枚举两两B点,设一个是u,一个是v

    若所有的点A都在线段u->v的左边,那么u->v建条边

    若所有的点A都在线段u->v的右边,那么v->u建条边

  最后就是flyod求一下最小环就行了

  时间复杂度O(n^3)

hdu6080(最小环)

原文:http://www.cnblogs.com/wmrv587/p/7359561.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!