c456: 5. 馬拉松
標籤 :
通過比率 : 100% (3 人 / 3 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-12-28 06:37

內容

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


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

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

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

F(S) = |S| min1≤i≤|S| Di

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

輸入說明

每一組測試資料有兩列, 其中第一列有兩個正整數N 和M (1 ≤ M ≤ N*(N-1)/2),
第二列有M 對正整數X1 Y1 X2 Y2 … XM YM,代表選手Xi 認識選手Yi (1 ≤ i ≤ M 且1 ≤ Xi < Yi
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
測資資訊:
記憶體限制: 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 ≤ 100,全部解出可獲19 分;
第二子題的測試資料中N ≤ 500,全部解出可獲38 分;
第三子題的測試資料中N ≤ 5000,全部解出可獲43 分。

標籤:
出處:
106學年度全國資訊學科能力競賽 [編輯:
icube (iCUbe)
]


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