幫你釐清一些細節
※ 引述《iamnotgm (伽藍之黑)》之銘言：
: 問題是這樣的
: 座標平面上有幾個炸彈
: 每個炸彈引爆時會炸出一個正方形的範圍
^^^^^^^^^^^^ 剛好在邊界上，會不會被炸？
: 任何在這個範圍內的其他炸彈會連鎖反應一起炸
: 給定N個炸彈的位置和爆炸範圍後
: 求點燃最少的炸彈把所有的炸彈炸光
: 我的解法是先找出每一顆炸彈可以炸到誰
^^^^^^^^^^^^^^^^^^^^ 這是一對多關聯
也許可以拆散，變成一對一關聯？
: 做出一張graph後找出不會被其他人炸到的炸彈先炸
^^^^^^^^^ 是單向的呢（有向圖），還是雙向的呢（無向圖）?
: 炸完後剩下來還沒引爆的炸彈應該就是存在於環上
^^^^
上一句「不會被其他人炸到的炸彈」
是不是也可以統一看做是環?
如果可以統一，就比較單純，不需要特例
: 先假定引爆A炸彈
: 之後如果再引爆B炸彈發現他會點燃A炸彈就把A炸彈拿掉
: 直到所有的炸彈都被主動或被其他炸彈引爆
: 這個樣子的解法會wrong answer
^^^^^^^^^^^^ 說不定是 1.奇葩的特例沒想到，例如0、大數、空白行
2.程式碼有bug，比如溢位、少印句點之類的
3.算法是對的，不過程式碼邏輯錯了
4.算法是錯的
5.judge測資壞了
: 但是我想不出來有什麼樣的case是我的演算法沒考慮到的
: 上網查了一下看到了一個解法叫做strongly connected component
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
有向的環 一群一群混疊在一起的環
這概念在書上從未明講，至少我看過的書都沒這樣講
: 可是我不懂這東西和這題的關聯性
^^^^^^
說不定是：1.你還沒抓到本題關鍵
2.你不熟悉scc
3.這題解法根本不是scc
要我來看的話，比較像是weakly connected component
或者是in-degree = 0那一類的東西
: 題目連結:
: https://icpcarchive.ecs.baylor.edu/external/48/4846.pdf
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 老實說我沒有看
應該沒關係吧？
: 先謝過各位了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.59.192.73
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1407733269.A.402.html
※ 編輯: DJWS (210.59.192.73), 08/11/2014 13:21:25