c456. 5. 馬拉松 - 高中生程式解題系統

內容

金氏運動公司打算舉辦一場馬拉松比賽，為了締造亮眼的完成比賽時間，金氏運動公司打算選擇性地邀請選手參賽。分析過往的數據資料，金氏運動公司觀察到以下二個現象：

(a) 對於任何一位選手，如果愈多他的朋友參賽，則他就能跑得愈快，所以傾向於找一群選手使得彼此互相認識的情況很多。因為認識是雙向的，如果 $P$ 認識 $Q$ ，則 $Q$ 認識 $P$ 。所以當我們說 $P$ 認識 $Q$ 時，等同於表示 $P$ 、 $Q$ 兩位互相認識。

(b) 如果參賽的選手當中，存在兩位選手 $P$ 和 $Q$ 彼此不認識，而且在參賽的選手當中無法找到 $t$ 位選手 $S_{1} 、 \dots 、 S_{t}$ ( $t$ 為任意大於 $0$ 的整數)，使得 $P$ 認識 $S_{1}$ ， $S_{1}$ 認識 $S_{2}$ ， $\dots$ ， $S_{t - 1}$ 認識 $S_{t}$ ， $S_{t}$ 認識 $Q$ ，則比賽將會有嚴重的惡性競爭，所以需要避免這樣的狀況。

現在金氏運動公司手上有一份 $N$ 位選手的名單以及一份顯示這 $N$ 位選手彼此之間是否認識的表單，現在的任務是從這 $N$ 位選手找出選手的子集合 $S = {P_{1}, P_{2}, \dots, P_{| S |}}$ ，使得 $S$ 沒有惡性競爭的狀況，而且讓以下影響因子 $F (S)$ 得到最大化，這影響因子的設計除了讓每位選手都認識夠多的參賽者，也兼顧了不讓參賽人數過少。

$F (S) = | S | m i n_{1 \leq i \leq | S |} D_{i}$ ，

其中 $D_{i}$ 表示選手 $P_{i}$ 所認識的人當中，有多少人在子集合 $S$ 裡面。在以下這個 $4$ 位選手的例子中，選 $S = {2, 3, 4}$ 比其他的選法有更高的 $F (S)$ 。

輸入說明

每一組測試資料有兩列，其中第一列有兩個正整數 $N$ 和 $M (1 \leq M \leq N * (N - 1) / 2)$ ，
第二列有 $M$ 對正整數 $X_{1} Y_{1} X_{2} Y_{2} \dots X_{M} Y_{M}$ ，代表選手 $X_{i}$ 認識選手 $Y_{i} (1 \leq i \leq M$ 且 $1 \leq X_{i} < Y_{i} \leq N)$ 。

輸出說明

對於每組測試資料，輸出最大的 $F (S)$ 。 $F (S)$ 這數字需獨自佔一列。

範例輸入 #1

輸入範例 1：
4 5
1 2 2 3 3 4 4 1 2 4

輸入範例 2：
4 4
1 2 2 3 3 4 2 4

輸入範例 3：
6 6
1 3 1 2 2 3 4 5 5 6 4 6

範例輸出 #1

輸出範例 1：
8

輸出範例 2：
6

輸出範例 3：
6

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (2%): 3.0s , <1K
公開測資點#1 (2%): 3.0s , <1M
公開測資點#2 (2%): 3.0s , <1K
公開測資點#3 (2%): 3.0s , <1M
公開測資點#4 (2%): 3.0s , <1K
公開測資點#5 (2%): 3.0s , <1M
公開測資點#6 (2%): 3.0s , <1M
公開測資點#7 (2%): 3.0s , <1M
公開測資點#8 (2%): 3.0s , <1M
公開測資點#9 (1%): 3.0s , <1M
公開測資點#10 (4%): 3.0s , <1M
公開測資點#11 (4%): 3.0s , <1M
公開測資點#12 (4%): 3.0s , <1M
公開測資點#13 (4%): 3.0s , <1M
公開測資點#14 (4%): 3.0s , <1M
公開測資點#15 (4%): 3.0s , <1M
公開測資點#16 (4%): 3.0s , <1M
公開測資點#17 (4%): 3.0s , <1M
公開測資點#18 (3%): 3.0s , <1M
公開測資點#19 (3%): 3.0s , <1M
公開測資點#20 (5%): 3.0s , <10M
公開測資點#21 (5%): 3.0s , <50M
公開測資點#22 (5%): 3.0s , <1M
公開測資點#23 (4%): 3.0s , <10M
公開測資點#24 (4%): 3.0s , <10M
公開測資點#25 (4%): 3.0s , <50M
公開測資點#26 (4%): 3.0s , <10M
公開測資點#27 (4%): 3.0s , <50M
公開測資點#28 (4%): 3.0s , <50M
公開測資點#29 (4%): 3.0s , >50M

提示：

本題共有三個子題，每一子題可有多筆測試資料：
第一子題的測試資料中 $N \leq 100$ ，全部解出可獲 19 分；
第二子題的測試資料中 $N \leq 500$ ，全部解出可獲 38 分；
第三子題的測試資料中 $N \leq 5000$ ，全部解出可獲 43 分。

標籤:

出處:

106學年度全國資訊學科能力競賽 [管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」