QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#22396. 地震損壞 2

Statistics

威斯康星發生了地震,波及 Farmer John 的農場!地震損壞了部分牧場,使它們無法通行。出人意料的是,沒有一條奶牛小路受損。

和往常一樣,農場由 $P$ 個牧場($1 \le P \le 3,000$,編號 $1..P$)及連接它們的 $C$ 條無向奶牛小路($1 \le C \le 20,000$,編號 $1..C$)組成。小路 $i$ 連接牧場 $a_{i}$ 和 $b_{i}$($1 \le a_{i} \le P; 1 \le b_{i} \le P$)。小路可能把 $a_{i}$ 連到它自身,也可能多次連接同一對牧場。牛棚位於牧場 1。

總共 $N$ 頭位於不同牧場的奶牛($1 \le N \le P$)依次用手機聯絡 Farmer John,傳送整數訊息 $report_{j}$($2 \le report_{j} \le P$)。它表示牧場 $report_{j}$ 未損壞,但這頭奶牛無法從那裡返回牛棚,因為找不到不經過損壞牧場的路徑。

所有奶牛報告完畢後,求至少有多少個牧場被損壞。

輸入格式

  • 第 1 行:三個以空格分隔的整數 $P$、$C$ 和 $N$。

  • 第 $2..C+1$ 行:第 $i+1$ 行以兩個整數 $a_{i}$ 和 $b_{i}$ 描述小路 $i$。

  • 第 $C+2..C+N+1$ 行:第 $C+1$ $+$ $j$ 行包含一個整數 $report_{j}$。

輸出格式

  • 第 1 行:一個數,表示損壞牧場的最少數量。

範例

輸入格式 1

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

輸出格式 1

1

說明

只有牧場 2 損壞就能產生這種情況。

題目作者:Hal Burch、Richard Peng,2008

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.