Problem:
Given a simple biconnected planar graph G(V, E) with vertex position (x, y)
Process queries: given simple cycle C, answer how many vertices is inside C?
比賽時沒有人 solve
雖然好像有點過難, 但真是一道好題
解法和 flow 有關, 不過不是要搵 maxflow
任意選一個在 boundary 的 vertex s
由 s 向每個 vertex 都 send 一個 unit flow, 用 DFS 可以輕鬆做到
可以看出, C 入面 vertex 的數目 = (Flow entering C) - (Flow leaving C)
計算時, 只要對每個 vertex 的 neighbors sort by polar, 就可以用 partial sum 搵 flow value
一直看不出這題和 flow 有關, 真的大開眼界了
Given a simple biconnected planar graph G(V, E) with vertex position (x, y)
Process queries: given simple cycle C, answer how many vertices is inside C?
比賽時沒有人 solve
雖然好像有點過難, 但真是一道好題
解法和 flow 有關, 不過不是要搵 maxflow
任意選一個在 boundary 的 vertex s
由 s 向每個 vertex 都 send 一個 unit flow, 用 DFS 可以輕鬆做到
可以看出, C 入面 vertex 的數目 = (Flow entering C) - (Flow leaving C)
計算時, 只要對每個 vertex 的 neighbors sort by polar, 就可以用 partial sum 搵 flow value
一直看不出這題和 flow 有關, 真的大開眼界了
No comments:
Post a Comment