Re: [問題] ACM 4846 (Strongly connected component?)
※ 引述《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
: 先謝過各位了
--
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCS/M d-(+) s:+ a- C++$ UL++B+ P++(++++) L+ E--@ W++ N? o? K? w(++)
!O M !V PS++(+++) PE++(+++) !Y PGP t+++ !5 !X R !tv b++ DI++ D+
G e+++>++++ h--* r% y+
------END GEEK CODE BLOCK------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 128.36.232.45
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1407694100.A.81A.html
→
08/11 02:10, , 1F
08/11 02:10, 1F
推
08/12 13:02, , 2F
08/12 13:02, 2F
→
08/12 13:04, , 3F
08/12 13:04, 3F
→
08/12 19:14, , 4F
08/12 19:14, 4F
→
08/12 19:15, , 5F
08/12 19:15, 5F
→
08/12 19:15, , 6F
08/12 19:15, 6F
討論串 (同標題文章)