问题是这样的 座标平面上有几个炸弹 每个炸弹引爆时会炸出一个正方形的范围 任何在这个范围内的其他炸弹会连锁反应一起炸 给定N个炸弹的位置和爆炸范围後 求点燃最少的炸弹把所有的炸弹炸光 我的解法是先找出每一颗炸弹可以炸到谁 做出一张graph後找出不会被其他人炸到的炸弹先炸 炸完後剩下来还没引爆的炸弹应该就是存在於环上 先假定引爆A炸弹 之後如果再引爆B炸弹发现他会点燃A炸弹就把A炸弹拿掉 直到所有的炸弹都被主动或被其他炸弹引爆 这个样子的解法会wrong answer 但是我想不出来有什麽样的case是我的演算法没考虑到的 上网查了一下看到了一个解法叫做strongly connected component 可是我不懂这东西和这题的关联性 题目连结: https://icpcarchive.ecs.baylor.edu/external/48/4846.pdf 先谢过各位了 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.34.198.188 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1407690876.A.54E.html ※ 编辑: iamnotgm (1.34.198.188), 08/11/2014 01:15:43