看板 [ Prob_Solve ]
討論串[問題] ACM 4846 (Strongly connected component?)
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] ACM 4846 (Strongly connected component?)
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者iamnotgm (伽藍之黑)時間10年前 (2014/08/11 01:14), 10年前編輯資訊
2
0
2
內容預覽:
問題是這樣的. 座標平面上有幾個炸彈. 每個炸彈引爆時會炸出一個正方形的範圍. 任何在這個範圍內的其他炸彈會連鎖反應一起炸. 給定N個炸彈的位置和爆炸範圍後. 求點燃最少的炸彈把所有的炸彈炸光. 我的解法是先找出每一顆炸彈可以炸到誰. 做出一張graph後找出不會被其他人炸到的炸彈先炸. 炸完後剩下
(還有274個字)
#2
Re: [問題] ACM 4846 (Strongly connected component?)
推噓1(1推 0噓 5→)留言6則，0人參與, 最新作者scwg ( )時間10年前 (2014/08/11 02:08), 編輯資訊
1
0
2
內容預覽:
試試看. 3. 6 4 1. 4 4 4. 8 4 4. 根據你第二步選出 A 炸彈的方法, 可能要把輸入順序調換一下.. 無論如何, 這個測資長這樣. _______________. | | _ | |. | B |A| C |. |____|_____|____|. 也就是 B, C 會互相引
(還有935個字)
#3
Re: [問題] ACM 4846 (Strongly connected component?)
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者DJWS (...)時間10年前 (2014/08/11 13:01), 10年前編輯資訊
0
0
2
內容預覽:
幫你釐清一些細節 ^^^^^^^^^^^^ 剛好在邊界上，會不會被炸？ ^^^^^^^^^^^^^^^^^^^^ 這是一對多關聯. 也許可以拆散，變成一對一關聯？ ^^^^^^^^^ 是單向的呢（有向圖），還是雙向的呢（無向圖）? ^^^^. 上一句「不會被其他人炸到的炸彈」. 是不是也可以統一看做
(還有629個字)
#4
Re: [問題] ACM 4846 (Strongly connected component?)
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者bleed1979 (十三)時間10年前 (2014/08/30 12:01), 10年前編輯資訊
0
0
2
內容預覽:
剛花了點時間來AC這題。. 原本採用SCC的Tarjan algorithm，但發覺和題意不太符合。. 因為我不需要找強連結的根。. 後來採用的是. 資料結構，. a.一整數陣列用來記錄最後有幾個團。. b.每一節點2個整數變數，變數1第幾個節點，變數2地幾個set，. c.另有每一節點的有向邊集合
(還有271個字)
首頁
上一頁
1
下一頁
尾頁