#P2932. [USACO09JAN] Earthquake Damage G

[USACO09JAN] Earthquake Damage G

题目描述

Wisconsin has had an earthquake that has struck Farmer John's farm! The earthquake has damaged some of the pastures so that they are unpassable. Remarkably, none of the cowpaths was damaged.

As usual, the farm is modeled as a set of P(1P30,000)P(1 \le P \le 30,000) pastures conveniently numbered 1P1\ldots P which are connected by a set of C(1C100,000)C (1 \le C \le 100,000) non-directional cowpaths conveniently numbered 1C1\ldots C. Cowpath ii connects pastures aia_i and bi(1aiP;1biP)b_i (1 \le a_i \le P; 1 \le b_i \le P). Cowpaths might connect aia_i to itself or perhaps might connect two pastures more than once. The barn is located in pasture 11.

A total of N(1NP)N (1 \le N \le P) cows (in different pastures) sequentially contact Farmer John via moobile phone with an integer message reportj(2reportjP)report_j (2 \le report_j \le P) that indicates that pasture reportjreport_j is undamaged but that the calling cow is unable to return to the barn from pasture reportjreport_j because she could not find a path that does not go through damaged pastures.

After all the cows report in, determine the minimum number of pastures (including ones that are uncrossable) from which it is not possible to return to the barn.

Note: Feedback on some of the test data will be provided on the first 5050 submissions.

输入格式

Line 11: Three space-separated integers: PP,CC,and NN.

Lines 2C+12\ldots C+1: Line i+1i+1 describes cowpath ii with two integers: aia_i and bib_i.

Lines C+2C+N+1C+2\ldots C+N+1: Line C+1+jC+1+j contains a single integer: reportjreport_j.

输出格式

Line 11: A single integer that is the minimum count of pastures from which a cow can not return to the barn (including the damaged pastures themselves)

题目大意

题目描述

农夫 John 的农场遭受了一场地震。有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用。FJ 的农场有 P(1P3×104)P(1 \le P \le 3\times 10^4) 个牛棚,编号 1P1\ldots PC(1C1×105)C(1 \le C \le 1\times 10^5) 条双向路径连接这些牛棚,编号为 1C1\ldots C,路经 ii 连接牛棚 aia_ibi(1aiP;1b_iP)b_i (1 \le a_i \le P;1 \le b\_i \le P)aia_ibib_i 可能相同,两个牛棚之间可能有多条路经。农庄在编号为 11 的牛棚。N(1NP)N (1 \le N \le P) 头在不同牛棚的牛通过手机短信告诉 FJ 它们的牛棚 reportj(2reportjP)report_j(2 \le report_j \le P) 没有损坏,但是它们无法通过路径和没有损坏的牛棚回到到农场。当 FJ 接到所有短信之后,找出最小的不可能回到农庄的牛棚数目。这个数目包括损坏的牛棚。注意:前 5050 次提交将提供在一些测试数据上的运行结果。

4 3 1 
1 2 
2 3 
3 4 
3 

3 

提示

Pasture 22 is damaged, resulting in cows in pastures 2,3,42, 3, 4 not being able to return to the barn.