TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

85.7% (12/14)

Submission's AC Ratio

55.1% (27/49)

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

Sample Input #1
1
3 4 5
1 2
1 3
2 1
2 3
3 4

Sample Input #2
1
2 2 3
1 1
2 2
1 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

Sample Output #1
3

Sample Output #2
2

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

For Testdata: 0 ~ 0, Score: 15
For Testdata: 1 ~ 1, Score: 19
For Testdata: 2 ~ 2, Score: 27
For Testdata: 3 ~ 3, Score: 29
For Testdata: 4 ~ 4, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 524288 65536
1 4000 524288 65536
2 4000 524288 65536
3 4000 524288 65536
4 4000 524288 65536