- 题目提供者 FarmerJohn2
- 评测方式 云端评测
- 标签 图的建立,建图 最小割 网络流 USACO 2009 高性能
- 难度 省选/NOI-
- 时空限制 1000ms / 128MB
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 (1 <= P <= 3,000)
pastures conveniently numbered 1..P which are connected by a set of C (1 <= C <= 20,000) non-directional cowpaths conveniently
numbered 1..C. Cowpath i connects pastures a_i and b_i (1 <= a_i <= P; 1 <= b_i <= P). Cowpaths might connect a_i to itself or perhaps might connect two pastures more than once. The barn is located in pasture 1.
A total of N (1 <= N <= P) cows (in different pastures) sequentially contacts Farmer John via moobile phone with an integer message report_j (2 <= report_j <= P) that indicates that pasture report_j is undamaged but that the calling cow is unable to return to the barn from pasture report_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 that are damaged.
N (1 <= N <= P) 只奶牛打来了求救电话，说她们的农场没有被摧毁，但是已经无法到达牛棚. 求出最少可能有多少牧场被摧毁.
* Line 1: Three space-separated integers: P, C, and N
* Lines 2..C+1: Line i+1 describes cowpath i with two integers: a_i and b_i
* Lines C+2..C+N+1: Line C+1+j contains a single integer: report_j输出格式：
* Line 1: One number, the minimum number of damaged pastures.
Only pasture 2 being damaged gives such a scenario.