PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] ACM 4846 (Strongly connected component?)

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2014/08/11 13:01)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/4 (看更多)

幫你釐清一些細節 ※ 引述《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