[問題] ACM 4846 (Strongly connected component?)
看板Prob_Solve (計算數學 Problem Solving)作者iamnotgm (伽藍之黑)時間10年前 (2014/08/11 01:14)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/4 (看更多)
問題是這樣的
座標平面上有幾個炸彈
每個炸彈引爆時會炸出一個正方形的範圍
任何在這個範圍內的其他炸彈會連鎖反應一起炸
給定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://www.ptt.cc/bbs/Prob_Solve/M.1407690876.A.54E.html
※ 編輯: iamnotgm (1.34.198.188), 08/11/2014 01:15:43
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
