Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DAMAGE - Động đất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/damage


Một trận động đất vừa xảy ra ở Wisconsin và tàn phá trang trại của nông dân John. Trận động đất đã phá hủy một số cánh đồng khiến cho đàn bò không thể đặt chân lên cánh đồng đó. Một điều khác thường là tất cả con đường nối các cánh đồng đều không bị tàn phá.

Như thường lệ, trang trại được xem là một tập hợp các P cánh đồng (1<=P<=30000) được đánh số từ 1 đến P và được nối với nhau bằng C đường đi hai chiều (1<=C<=100000) đánh số từ 1 đến C. Đường đi thứ i nối hai cánh đồng a_i và b_i (1<=a_i b_i<=P). Chú ý là các đường đi có thể nối cánh đồng a_i với chính nó hoặc giữa 2 cánh đồng có thể có nhiều đường đi. Chuồng bò được đặt ở cánh đồng 1.

Có N con bò (1<=N<=P) ở các cánh đồng khác nhau gọi về cho FJ và thông báo 1 số nguyên report_j (2<=report_j<=P) có nghĩa là cánh đồng report_j thỏa 2 điều kiện: + Cánh đồng report_j không bị tàn phá + Con bò đứng ở cánh đồng report_j không thể về được cánh đồng 1 vì trên đường đi có một số cánh đồng bị tàn phá và không thể đi qua các cánh đồng đó

Cho biết thông tin của N con bò, hãy xác định số lượng ít nhất các cánh đồng sao cho từ các cánh đồng đó không thể về được cánh đồng 1 (bao gồm luôn những cánh đồng bị phá hủy)

Dữ liệu

  • Dòng đầu chứa 3 số nguyên: P, C và N
  • C dòng sau mỗi dòng chứa 2 số a_i và b_i mô tả đường nối thứ i nối hai cánh đồng a_i và b_i
  • N dòng sau mỗi dòng chứa một số nguyên là thông tin của các con bò

Kết quả

Gồm 1 dòng duy nhất là số lượng ít nhất các cánh đồng không về được cánh đồng 1.

Ví dụ

Dữ liệu
4 3 1
1 2
2 3
3 4
3

Kết quả
3

Giải thích

Cánh đồng 2 bị phá hủy, vậy các con bò ở cánh đồng 2,3,4 sẽ không thể về chuồng


Được gửi lên bởi:Jimmy
Ngày:2009-01-15
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO January 2009 - Gold Division
Translated by duyhung123abc

hide comments
2018-09-03 17:05:50
nhật hào sạch
2018-06-23 18:49:17
test : 7 7 1
1 2
2 3
3 4
4 7
3 5
5 6
6 7
7
Kết quả test này phải ra 5 nhưng khi theo cách chấm này thì ra 3. Không biết mình có nhầm lẫn không?
2018-04-19 08:20:04
greedy
2015-12-31 20:23:22 Sơn Tùng M-TP
Thật là tình cờ! :)
2015-07-10 17:05:21 there's no salvation for me...
tưởng gì siêu dễ.... làm max đơn giản.... mất công ngồi nghĩ cả buổi...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.