c455: 4. 警力配置
標籤 :
通過比率 : 83% (5 人 / 6 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-12-28 00:04

內容

某警察局將負責巡邏A城市的k個區域R1, R2, … , Rk。局長下令將員警分成兩組:
X組有p位員警(以x1, x2, … , xp表示) 而Y組有q位員警(以y1, y2, … , yq表示)。每個區域
會有兩個員警負責巡邏,而且每個員警至少要巡邏一個區域。X組有p位員警和Y組有q位員警
可構成警力配置圖:此圖有p + q個節點(vertices)和k個邊(edges),其中p + q個節點對應p + q位員警,
而每條配置圖的邊Ri = (xj, yl)則表示員警xj和yl負責巡邏區域Ri

為了有效管理及節省開支,局長希望從p + q位員警中選出若干位組長來達成一項特別任務,
這項任務需要滿足一個條件:對負責巡邏任一個區域的兩位員警而言,至少要有一位組長。
給定X組有p位員警、Y組有q位員警、k個區域及每個區域負責巡邏的兩位員警,
請寫一支程式幫局長計算最少需幾位組長來達成上述任務。

範例說明:假設X組有3位員警x1, x2, x3,Y組有3 位員警y1, y2, y3來巡邏7個區域
R1, R2, … , R7,其中R1 = (x1, y1), R2 = (x2, y1), R3 = (x2, y3), R4 = (x3, y3),
R5 = (x3, y2), R6 = (x1, y2), R7 = (x3, y1)(如圖一),則局長可選y1, y2, y3來擔任組長(注意選法不是唯一),
且只選兩個組長將無法達成任務,故此範例的解答為3。

輸入說明

第一行有1個不大於10的數字代表此子題測資的數目。接下來每組測資的第一行有3個數字,
代表p值、q值與k值,任兩個數字以空白隔開。第二行起接下來k行代表k個區域,
每個區域對應2個數字(任兩個數字以空白隔開):第一個數字代表x組的員警編號;第二個數字代表y組的員警編號。

輸出說明

針對所輸入的資料,輸出能滿足任務的最小的組長個數。

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

輸入範例 2:
1
2 2 3
1 1
2 2
1 2

輸入範例 3:
1
5 4 8
1 1
1 4
2 1
3 2
3 4
4 4
5 1
5 3
範例輸出
輸出範例 1:
3

輸出範例 2:
2

輸出範例 3:
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (15%): 4.0s , <1K
公開 測資點#1 (19%): 4.0s , <1M
公開 測資點#2 (27%): 4.0s , <50M
公開 測資點#3 (29%): 4.0s , <1M
公開 測資點#4 (10%): 4.0s , <50M
提示 :

本題共有五個子題,每一子題可有多筆測試資料:
第一子題的測試資料 1 ≤ p+q ≤ 20、1 ≤ k ≤ 100,全部解出可獲15 分。
第二子題的測試資料警力配置圖為一條路徑(path),1 ≤ p ≤ 1500、1 ≤ q ≤ 1500、1 ≤ k ≤ p+q-1,全部解出可獲19 分。
第三子題的測試資料警力配置圖為連結圖(connected)且不存在環路(cycle)。
圖形為連結圖代表此圖的任意兩個不同的節點皆存在一條路徑;而環路表示起點和終點為同一節點的路徑。
1 ≤ p ≤ 100000、1 ≤ q ≤ 100000、1 ≤ k ≤ 210000。全部解出可獲27 分。
第四子題的測試資料1 ≤ p ≤ 500、1 ≤ q ≤ 500、1 ≤ k ≤ 5000,全部解出可獲29 分。
第五子題的測試資料1 ≤ p ≤ 1500、1 ≤ q ≤ 1500、1 ≤ k ≤ 230000,全部解出可獲10 分。

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


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