在唯一神 olmrgcsi 的領土上,人類種 rgnerdplayer 和神靈種 baluteshih 正在車輪戰。
這次的遊戲是競程大地遊戲。遊戲地圖是一個可以被視為二維平面的沙漠。唯一神 olmrgcsi 在沙漠上的
但是眾所周知,Atcoder Grand Contest 對神靈種比 div3 對人類種還要簡單,因此這
請問 rgnerdplayer 最少需要多少魔法石才能夠取勝?
TL:DR:以圖論的術語來說,你有一個平面圖且平面鑲嵌已知,最少要刪掉幾條邊才能使圖不是連通的?
Definitions and Hints:
平面圖 (planar graph) 的定義是存在一種平面鑲嵌 (plane graph/planar embedding) 的圖。平面鑲嵌的定義是把圖的點和邊畫在平面上的一種方式,使得任兩條邊不會在端點以外相交。簡單 (simple) 圖的定義是沒有重邊或自環的圖。特別的,本題給定的平面鑲嵌中每一條邊都是一條直線。
依據歐拉公式
輸入第一行兩個個正整數
接著
接著
輸出一行包含一個整數,代表問題的答案。
IOICamp 2023 Day5 pI
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資。 | 0 |
2 | 3~22 | 5 | |
3 | 3~50 | 20 | |
4 | 51~55 | 答案只會是 |
2 |
5 | 51~89 | 答案小於等於 |
5 |
6 | 51~113 | 答案小於等於 |
13 |
7 | 3~113 | 無特別限制。 | 55 |