刚花了点时间来AC这题。 原本采用SCC的Tarjan algorithm，但发觉和题意不太符合。 因为我不需要找强连结的根。 後来采用的是 资料结构， a.一整数阵列用来记录最後有几个团。 b.每一节点2个整数变数，变数1第几个节点，变数2地几个set， c.另有每一节点的有向边集合。 d.函数内为类SPFA的队列。 algo: 1.初始化给n个炸弹标记1 ~ N，变数1和变数2值一样。 2.loop，如果该节点的变数1和变数2相等，进入3.，否则5. 3.pop出来队列头并且引爆其他炸弹，若其他炸弹的尚未在队列里， 且其他炸弹的变数2不等於此节点的变数2， 则更新其他炸弹的变数2等於此节点的变数2，将其他炸弹放进队列。 4.队列不为空重复3. 5.loop所有节点，标记阵列[变数2的值] = 1。 6.loop整数阵列找出有几个团(有几个1)。 7.结束。 ※ 引述《scwg ( )》之铭言： : ※ 引述《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 : : 先谢过各位了 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.135.203.156 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1409371271.A.A04.html ※ 编辑: bleed1979 (220.135.203.156), 08/30/2014 12:01:57