1978 . 邀請函（Invitation）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

66.7% (26/39)

Submission's AC Ratio

25.9% (121/468)

Tags

TOI 2017-TOI-3rd graph search

Description

古老的米克斯王國共住了 n 個米克斯人，每個米克斯人都有自己的住所，住所編號為 0, 1, …, n – 1，任兩位米克斯人的住所間可能有雙向的通道、也可能沒有通道（但不會只有單向的通道）。米克斯國王常常舉辦全國性會議，他希望越多人出席越好，但被邀請出席者一定要符合一個特殊規定，即若兩位米克斯人的住所間有通道，則其中至多只有一人會受到邀請。給定 n 與所有通道，下次舉辦全國性會議時，總共要印製幾張邀請函？

Input Format

測資的第一行為住所總數 n，n 為一正整數，且住所編號為 0, 1, …, n – 1。第二行是總通道數 m。接下來的 m 行中，每行有兩個正整數 i, j（以空白區隔），代表住所 i 與住所 j 之間有一通道。

子任務（測資） 額外限制 分數
1 (0~4) $N\leq 24$ 10
2 (0~9) $N\leq 40$ 25
3 (10~14) $N\leq 80$為偶數，而且每條通道連接住所 {0, 1, …, n/2 – 1} 與 {n/2, n/2 + 1, …, n – 1} 各其中之一。 40
4 (0~22) $N\leq 80$ 25

Output Format

請輸出下次全國性會議舉辦時所需印製邀請卡數量。

Sample Input 1

6
6
0 3
1 5
3 2
2 5
0 4
1 0

Sample Output 1

3

Sample Input 2

7
8
6 5
0 3
2 6
3 5
1 4
1 2
3 4
2 3

Sample Output 2

4

Hints

經測試發現本處的測資較強。為了模擬模考時的難度，時限有作相應的放寬。

Problem Source

題目取自2017 TOI選訓第三次模擬考pD
Problem Set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~4 10
2 0~9 25
3 10~14 40
4 0~22 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1900 262144 262144 1 2 4
1 1900 262144 262144 1 2 4
2 1900 262144 262144 1 2 4
3 1900 262144 262144 1 2 4
4 1900 262144 262144 1 2 4
5 1900 262144 262144 2 4
6 1900 262144 262144 2 4
7 1900 262144 262144 2 4
8 1900 262144 262144 2 4
9 1900 262144 262144 2 4
10 1900 262144 262144 3 4
11 1900 262144 262144 3 4
12 1900 262144 262144 3 4
13 1900 262144 262144 3 4
14 1900 262144 262144 3 4
15 2900 262144 262144 4
16 1900 262144 262144 4
17 2900 262144 262144 4
18 1900 262144 262144 4
19 1900 262144 262144 4
20 2900 262144 262144 4
21 2900 262144 262144 4
22 2900 262144 262144 4
Submit
Back to Top