1376 . 搭擋問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

94.7% (36/38)

Submission's AC Ratio

69.7% (53/76)

Tags

CKsum 2008-CKsum-2nd

Description

　　在大不列顛軍中有所謂的搭擋制度，通常是由老兵搭配新兵，而且一個老兵只能搭配一個新兵，新兵亦同。

　　但也有人之間根本無法溝通，所以無法搭擋。

　　現在給你一些老兵與新兵的能否搭擋的關係表，請問最多可以湊出多少搭擋？

Input Format

只有一組測試資料。

第一行為兩個數字，n，m分別代表有幾個老兵與新兵(也就是老兵新兵人數都為n) 以及幾對人之間可以互相搭擋。

(0≦n≦10，0≦m≦100)

接著有m行，每行有兩個數字，x，y，代表老兵x與新兵y搭擋。

(0≦x，y≦n-1)

Output Format

輸出最好的情形能有幾對搭擋。

Sample Input 1

3 4
0 0
0 2
1 1
2 1

Sample Output 1

2

Hints

※2008/07/10 測資敘述修正 by ggm，感謝 shik。

Problem Source

原TIOJ1376 / 快樂暑假營第二次練習比賽。
(Maximum Matching Problem) Problem Setter：ggm

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
Submit
Back to Top