某警察局將負責巡邏 $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
本題共有五個子題,每一子題可有多筆測試資料:
第一子題的測試資料 $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 分。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
19297 | lawrence9104 ... (l4wr3nc3) | c455 | 2118 | 2019-09-23 23:38 | |
14978 | lltzpp (lltzpp) | c455 | 2593 | 2018-08-26 10:02 |