TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

86.6% (97/112)

Submission's AC Ratio

28.9% (190/657)

Tags

Description

某警察局將負責巡邏 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_i, y_i)$ 則表示員警 $x_i$ 和 $y_i$ 負責巡邏區域 $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。

Input Format

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

Output Format

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

Sample Input 1

1
3 4 5
1 2
1 3
2 1
2 3
3 4

Sample Output 1

3

Sample Input 2

1
2 2 3
1 1
2 2
1 2

Sample Output 2

2

Sample Input 3

1
5 4 8
1 1
1 4
2 1
3 2
3 4
4 4
5 1
5 3

Sample Output 3

4

Hints

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

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第四題

Subtasks

No. Testdata Range Score
1 0 15
2 1 19
3 2 27
4 3 29
5 4 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 262144 1
1 4000 524288 262144 2
2 4000 524288 262144 3
3 4000 524288 262144 4
4 4000 524288 262144 5