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

最近更新 : 2018-01-29 17:33

內容

某警察局將負責巡邏 $A$ 城市的 $k$ 個區域 $R_1, R_2, \ldots, R_k$。局長下令將員警分成兩組: $X$ 組
有 $p$ 位員警(以 $x_1, x_2, \ldots, x_p$ 表示) 而 $Y$ 組有 $q$ 位員警(以 $y_1, y_2, \ldots, y_q$ 表示)。每個區域會有
兩個員警負責巡邏,而且每個員警至少要巡邏一個區域。 $X$ 組有 $p$ 位員警和 $Y$ 組有 $q$ 位員警
可構成警力配置圖:此圖有 $p + q$ 個節點(vertices)和 $k$ 個邊(edges),其中 $p + q$ 個節點
對應 $p + q$ 位員警,而每條配置圖的邊 $R_i = (x_j, y_l)$ 則表示員警 $x_j$ 和 $y_l$ 負責巡邏區域 $R_i$。

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

範例說明:假設 $X$ 組有 $3$ 位員警 $x_1, x_2, x_3$,$Y$ 組有 $3$ 位員警 $y_1, y_2, y_3$ 來巡邏 $7$ 個區域
$R_1, R_2, \ldots, R_7$,其中 $R_1 = (x_1, y_1), R_2 = (x_2, y_1), R_3 = (x_2, y_3), R_4 = (x_3, y_3),$ 
$R_5 = (x_3, y_2), R_6 = (x_1, y_2), R_7 = (x_3, y_1)$(如圖一),則局長可選 $y_1, y_2, y_3$ 來擔任組長(注意選法不是唯一),
且只選兩個組長將無法達成任務,故此範例的解答為 $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 \le p+q \le 20$、$1 \le k \le 100$,全部解出可獲 15 分。
第二子題的測試資料警力配置圖為一條路徑(path),$1 \le p \le 1500$、$1 \le q \le 1500$、$1 \le k \le p+q-1$,全部解出可獲 19 分。
第三子題的測試資料警力配置圖為連結圖(connected)且不存在環路(cycle)。
圖形為連結圖代表此圖的任意兩個不同的節點皆存在一條路徑;而環路表示起點和終點為同一節點的路徑。
$1 \le p \le 100000$、$1 \le q \le 100000$、$1 \le k \le 210000$。全部解出可獲27 分。
第四子題的測試資料 $1 \le p \le 500$、$1 \le q \le 500$、$1 \le k \le 5000$,全部解出可獲29 分。
第五子題的測試資料 $1 \le p \le 1500$、$1 \le q \le 1500$、$1 \le k \le 230000$,全部解出可獲10 分。

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


編號 身分 題目 主題 人氣 發表日期
14978
lltzpp (lltzpp)
c455
119 2018-08-26 10:02