※ 引述《iamnotgm (伽蓝之黑)》之铭言： : 问题是这样的 : 座标平面上有几个炸弹 : 每个炸弹引爆时会炸出一个正方形的范围 : 任何在这个范围内的其他炸弹会连锁反应一起炸 : 给定N个炸弹的位置和爆炸范围後 : 求点燃最少的炸弹把所有的炸弹炸光 : 我的解法是先找出每一颗炸弹可以炸到谁 : 做出一张graph後找出不会被其他人炸到的炸弹先炸 : 炸完後剩下来还没引爆的炸弹应该就是存在於环上 : 先假定引爆A炸弹 : 之後如果再引爆B炸弹发现他会点燃A炸弹就把A炸弹拿掉 : 直到所有的炸弹都被主动或被其他炸弹引爆 : 这个样子的解法会wrong answer : 但是我想不出来有什麽样的case是我的演算法没考虑到的 试试看 3 6 4 1 4 4 4 8 4 4 根据你第二步选出 A 炸弹的方法, 可能要把输入顺序调换一下. 无论如何, 这个测资长这样 _______________ | | _ | | | B |A| C | |____|_____|____| 也就是 B, C 会互相引爆, 也都会引爆 A, 但是 A 爆炸不会有连锁反应 因此问题出在这一句: 炸完後剩下来还没引爆的炸弹应该就是存在於环上 应该要修正为: 炸完後剩下来还没引爆的炸弹应该就是存在於环上, 或者会被环上任一个炸弹的连锁反应引爆 因此第二步要确定引爆的 A 炸弹 1. 确实在环上 不过这样还不太够, 考虑下面这个 graph C -> A ^ ^ | | v v D B -> E 上面那个条件确保我们不会选到 E, 但是我们仍然可能选到 A 或 B (正解为引爆一次, C 或 D, 引爆 A, B, 或 E 都需要两次以上) 因此还需要第二个条件 2. 不会被另一个环上任一个炸弹的连锁反应引爆 到这里有没有发现第二步和第一步几乎一模一样, 只不过把『炸弹』换成『环』? (第一步的两个条件是: 1. 确实是一个炸弹 2. 不会被另一个炸弹引爆 ) 因此我们可以把图上每个环视为一个大炸弹, 然後数数看有几个 (大) 炸弹不会 被连锁反应炸到, 需要手动引爆, 就是答案了. 这麽一来问题就变成, 要怎麽找出所有的『环』呢? 要注意所谓的『环』不一定是一个圈喔! A <- B -> D | ^ | | | | +--> C <--+ 是两个圈, 但是应该要视为一个『环』, 因为引爆其中任意一个, 全部四个都会爆炸 上面这个性质其实就是 strongly connected component 的定义! 所以研究看看 strongly connected component 的性质和如何找出他们吧! : 上网查了一下看到了一个解法叫做strongly connected component : 可是我不懂这东西和这题的关联性 : 题目连结: : https://icpcarchive.ecs.baylor.edu/external/48/4846.pdf : 先谢过各位了 -- -----BEGIN GEEK CODE BLOCK----- Version: 3.12 GCS/M d-(+) s:+ a- C++$ UL++B+ P++(++++) L+ E--@ W++ N? o? K? w(++) !O M !V PS++(+++) PE++(+++) !Y PGP t+++ !5 !X R !tv b++ DI++ D+ G e+++>++++ h--* r% y+ ------END GEEK CODE BLOCK------ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 128.36.232.45 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1407694100.A.81A.html