• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3041 – Asteroids

    ACM-POJ EXP 170阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    解题思路

    把方阵看做一个特殊的二分图(以行列分别作为两个顶点集V1、V2,其中| V1|=| V2|)
      然后把每行x或者每列y看成一个点,而障碍物(x,y)可以看做连接x和y的边。按照这种思路构图后。问题就转化成为选择最少的一些点(x或y),使得从这些点与所有的边相邻,其实这就是最小点覆盖问题
      再利用二分图最大匹配的Konig定理:最小点覆盖数 = 最大匹配数
    (备注:最小点覆盖:假如选了一个点就相当于覆盖了以它为端点的所有边,那么需要选择最少的点来覆盖图的所有的边。)


    因此本题自然转化为求 二分图的最大匹配 问题
      求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。
      但是这个算法的时间复杂度为边数的指数级函数,
      所以需要寻求一种更加高效的算法——用增广路求最大匹配的方法(匈牙利算法)


    增广路的定义(也称增广轨或交错轨):
      若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。

    由增广路的定义可以推出下述三个结论
        1、P的路径个数必定为奇数,第一条边和最后一条边都不属于M。
        2、将M和P进行取反操作可以得到一个更大的匹配M
          (反操作:把P中的 匹配边 与 非匹配边 互换)
        3、M为G的最大匹配当且仅当不存在M的增广路径P


    匈牙利算法步骤
      1、 置M为空
      2、 找出一条增广路径P,通过异或操作获得更大的匹配M’代替M
      3、 重复(2)操作直到找不出增广路径为止

    转载请注明:EXP 技术分享博客 » POJ3041 – Asteroids

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址