P2932 [USACO09JAN] Earthquake Damage G
题目描述
威斯康星州发生了一场地震,影响了 Farmer John 的农场!地震损坏了一些牧场,使它们无法通行。值得注意的是,没有一条牛道受到损坏。
像往常一样,农场被建模为一组编号为 $1\ldots P$ 的 $P(1 \le P \le 30,000)$ 个牧场,这些牧场通过一组编号为 $1\ldots C$ 的 $C (1 \le C \le 100,000)$ 条无向牛道连接。牛道 $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$ 未受损,但打电话的牛无法从牧场 $report_j$ 返回谷仓,因为它找不到不经过受损牧场的路径。
在所有牛报告后,确定无法返回谷仓的最小牧场数量(包括那些不可通行的牧场)。
注意:在前 $50$ 次提交中,将提供部分测试数据的反馈。
输入格式
第 $1$ 行:三个用空格分隔的整数:$P$,$C$ 和 $N$。
第 $2\ldots C+1$ 行:第 $i+1$ 行描述牛道 $i$,包含两个整数:$a_i$ 和 $b_i$。
第 $C+2\ldots C+N+1$ 行:第 $C+1+j$ 行包含一个整数:$report_j$。
输出格式
第 $1$ 行:一个整数,表示无法从牧场返回谷仓的最小牧场数量(包括受损的牧场本身)。
说明/提示
牧场 $2$ 受损,导致牧场 $2, 3, 4$ 的牛无法返回谷仓。(由 ChatGPT 4o 翻译)