在唯一神 olmrgcsi 的領土上,人類種 rgnerdplayer 和神靈種 baluteshih 正在車輪戰。
這次的遊戲是競程大地遊戲。遊戲地圖是一個可以被視為二維平面的沙漠。唯一神 olmrgcsi 在沙漠上的 $n$ 個位置放置了據點,每一個據點都有一道難度堪比 Atcoder Grand Contest G 題難度的競程題目。第 $i$ 個據點的位置是 $(x_i, y_i)$,解開據點的題目就可以佔領該據點。地圖上還有 $m$ 條直線道路,每一條道路連結兩個據點。每一條道路在兩端點以外不會路過其他的據點,任兩條道路也不會在端點以外的地方相交。rgnerdplayer 會先選擇一個出發點,接著 baluteshih 會選擇一個不同的出發點。兩位玩家都要透過道路到達 $n$ 個據點並 AC 據點中的問題,AC 的數量多者贏得勝利,如果數量相同則是 rgnerdplayer 勝利。
但是眾所周知,Atcoder Grand Contest 對神靈種比 div3 對人類種還要簡單,因此這 $n$ 道題目 baluteshih 都可以在兩秒內做出來。沒有勝算的 rgnerdplayer 在危急時刻想起了唯一神 olmrgcsi 曾經給他一些魔法石,每一顆魔法石可以用來炸掉任何一條道路。由於可能還有派上用場的機會,rgnerdplayer 想要用最少的魔法石,讓 baluteshih 無法移動到所有的據點。由於 rgnerdplayer 有先選擇起點的權利,他就可以贏得這場比賽了,即使這 $n$ 道題目有可能會花他一輩子的時間。
請問 rgnerdplayer 最少需要多少魔法石才能夠取勝?
TL:DR:以圖論的術語來說,你有一個平面圖且平面鑲嵌已知,最少要刪掉幾條邊才能使圖不是連通的?
Definitions and Hints:
平面圖 (planar graph) 的定義是存在一種平面鑲嵌 (plane graph/planar embedding) 的圖。平面鑲嵌的定義是把圖的點和邊畫在平面上的一種方式,使得任兩條邊不會在端點以外相交。簡單 (simple) 圖的定義是沒有重邊或自環的圖。特別的,本題給定的平面鑲嵌中每一條邊都是一條直線。
依據歐拉公式 $v - e + f = 2$ 可以證明簡單連通平面圖有 $e \leq 3v - 6$,其中 $v$ 是點的數量、$e$ 是邊的數量、$f$ 是平面被劃分成的區域的數量(包含外側延伸到無限大的那個區域)。
輸入第一行兩個個正整數 $n, m$,分別代表地圖上據點的數量,以及地圖上道路的數量。
接著 $n$ 行每一行有兩個正整數 $x_i, y_i$,代表第 $i$ 個據點的位置。
接著 $m$ 行每一行有兩個正整數行 $u_i, v_i$,代表編號 $u_i, v_i$ 的據點中間連了一條直線的道路。
輸出一行包含一個整數,代表問題的答案。
IOICamp 2023 Day5 pI
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資。 | 0 |
2 | 3~22 | $n \leq 9$。 | 5 |
3 | 3~50 | $n \leq 60$。 | 20 |
4 | 51~55 | 答案只會是 $0$ 或 $1$。 | 2 |
5 | 51~89 | 答案小於等於 $2$。 | 5 |
6 | 51~113 | 答案小於等於 $3$。 | 13 |
7 | 3~113 | 無特別限制。 | 55 |