金氏運動公司打算舉辦一場馬拉松比賽,為了締造亮眼的完成比賽時間,金氏運動公司
打算選擇性地邀請選手參賽。分析過往的數據資料,金氏運動公司觀察到以下二個現象:
(a) 對於任何一位選手,如果愈多他的朋友參賽,則他就能跑得愈快,所以傾向於找一
群選手使得彼此互相認識的情況很多。因為認識是雙向的,如果 $P$ 認識 $Q$,則 $Q$ 認
識 $P$。所以當我們說 $P$ 認識 $Q$ 時,等同於表示 $P$、$Q$ 兩位互相認識。
(b) 如果參賽的選手當中,存在兩位選手 $P$ 和 $Q$ 彼此不認識,而且在參賽的選手當中無
法找到 $t$ 位選手 $S_1、\ldots、S_t$ ($t$ 為任意大於 $0$ 的整數),使得 $P$ 認識 $S_1$,$S_1$ 認識
$S_2$,$\ldots$,$S_{t-1}$ 認識 $S_t$,$S_t$ 認識 $Q$,則比賽將會有嚴重的惡性競爭,所以需要避免這樣的狀況。
現在金氏運動公司手上有一份 $N$ 位選手的名單以及一份顯示這N 位選手彼此之間是否
認識的表單,現在的任務是從這 $N$ 位選手找出選手的子集合 $S = \{P_1, P_2, \ldots, P_{\left\lvert S \right\rvert}\}$,使得 $S$ 沒
有惡性競爭的狀況,而且讓以下影響因子 $F(S)$ 得到最大化,這影響因子的設計除了讓每位選
手都認識夠多的參賽者,也兼顧了不讓參賽人數過少。
$F(S) = \left\lvert S \right\rvert min_{1 \le i \le \left\lvert S \right\rvert}$,
其中 $D_i$ 表示選手 $P_i$ 所認識的人當中,有多少人在子集合 $S$ 裡面。 在以下這個 $4$ 位選手的
例子中,選 $S = \{2, 3, 4\}$ 比其他的選法有更高的 $F(S)$。
每一組測試資料有兩列, 其中第一列有兩個正整數 $N$ 和 $M (1 \le M \le N*(N-1)/2)$,
第二列有 $M$ 對正整數 $X_1 Y_1 X_2 Y_2 \ldots X_M Y_M$,代表選手 $X_i$ 認識選手 $Y_i (1 \le i \le M$ 且 $1 \le X_i \lt Y_i \le N)$。
對於每組測試資料,輸出最大的 $F(S)$。$F(S)$ 這數字需獨自佔一列。
輸入範例 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: 8 輸出範例 2: 6 輸出範例 3: 6
本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料中 $N \le 100$,全部解出可獲19 分;
第二子題的測試資料中 $N \le 500$,全部解出可獲38 分;
第三子題的測試資料中 $N \le 5000$,全部解出可獲43 分。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |