首页 > 代码库 > hdu6080(最小环)

hdu6080(最小环)

题目

  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(最小环)