2002 - MỜI KHÁCH DỰ TIỆC(DÀNH CHO HỌC SINH THPT)CÔNG TY TRÁCH...

Bài 100/2002 - Mời khách dự tiệc

(Dành cho học sinh THPT)

Công ty trách nhiệm hữu hạn “Vui vẻ” có n cán bộ đánh số từ 1 đến n. Cán bộ i có đánh giá độ vui tính là vi

(i = 1, 2, ..., n). Ngoại trừ Giám đốc Công ty, mỗi cán bộ có 1 thủ trưởng trực tiếp của mình.

Bạn chỉ cần giúp Công ty mời một nhóm cán bộ đến dự dạ tiệc “Vui vẻ” sao cho trong số những người được

mời không đồng thời có mặt nhân viên và thủ trưởng trực tiếp và đồng thời tổng đánh giá độ vui tính của

những người dự tiệc là lớn nhất.

Giả thiết rằng mỗi một thủ trưởng có không quá 20 cán bộ trực tiếp dưới quyền.

Dữ liệu: Vào từ file văn bản GUEST.INP

- Dòng đầu tiên ghi số cán bộ của Công ty: n (1 < n < 1001);

- Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên dương ti, vi; trong đó ti là số hiệu của thủ trưởng

trực tiếp và vi là độ vui tính của cán bộ i (i = 1, 2, ..., n). Quy ước ti = 0 nếu i là số hiệu của Giám đốc Công

ty.

Kết quả: Ghi ra file văn bản GUEST.OUT

- Dòng đầu tiên ghi hai số m, v; trong đó m là tổng số cán bộ được mời còn v là tổng độ vui tính của các cán

bộ được mời dự tiệc;

- Dòng thứ i trong số m dòng tiếp theo ghi số hiệu của cán bộ được mời thứ i (i = 1, 2, ..., m).

Ví dụ:

GUEST.INP GUEST.OUT

2 7

3

1

0 3

1 6

2 4

7

3 63

0 1

1 1

4

1 12

5

2 50

2 1

3 1

(Đề ra của bạn Lưu Văn Minh)

Phần II: LỜI GIẢI