SKIVER1 - Skiers

Vương quốc nọ có N thành phố, biết rằng thành phố 1 chỉ có thể đến được các thành phố khác mà không thành phố nào đến được thành phố 1, thành phố N không đến được thành phố nào khác mà chỉ có thành phố khác đến thành phố này. Trong vương quốc 2 thành phố bất kì được nối với nhau thông qua không quá 1 con đường một chiều. Quanh năm vương quốc ngập trong tuyết, nhà vua muốn tuyển một đội trượt tuyết gồm ít người nhất sao cho mỗi người đều xuất phát từ thành phố 1, qua các thành phố trung gian rồi dừng lại tại thành phố N thỏa mãn các con đường một chiều được thăm bởi ít nhất 1 thành viên trong đội.

Dữ liệu

  • Dòng đầu ghi số nguyên dương N, số thành phố (N < 5001).
  • N -1 dòng sau mỗi dòng mô tả thông tin về mỗi thành phố từ 1 đến N - 1, số đầu tiên của mỗi dòng ghi số K là lượng thành phố mà thành phố đó có thể đi tới, K số tiếp theo là chỉ số các thành phố đó.

Kết qủa

Ghi ra số nhỏ nhất các thành viên trong đội.

Ví dụ

 
Dữ liệu: 
15
5 3 5 9 2 4
1 9
2 7 5
2 6 8
1 7
1 10
2 14 11
2 10 12
2 13 10
3 13 15 12
2 14 15
1 15
1 15
1 15
Kết qủa 
8 


Được gửi lên bởi:Trần Hải Đăng
Ngày:2010-05-15
Thời gian chạy:1s
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ừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:Chút thay đổi từ bài POI 2001

hide comments
2016-10-07 05:24:16


Last edit: 2016-10-07 05:24:37
2012-06-29 15:11:55 T-7
PS có thể cập nhật thêm về số lượng con đường 1 chiều tối đa được ko ?
2012-05-02 07:38:10 VOJ Team
Statement & test cases updated. (N < 5001)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.