Câu hỏi 73
Cho $N$ và $s$ là các số nguyên dương với $N \gt s$. Trong khu công viên Taipower có một số tòa nhà, trong đó đúng $N$ tòa là nhà máy điện, và thêm một tòa là trụ sở chính. Giữa một số cặp tòa nhà có các đường dây chỉ truyền điện theo một chiều, thỏa mãn:
(i) mọi đường dây nối với một nhà máy điện chỉ truyền điện ra khỏi nhà máy đó;
(ii) với mỗi tòa nhà không phải trụ sở chính, tồn tại duy nhất một dãy đường dây tạo thành một lộ trình từ tòa nhà đó đến trụ sở chính.
Một tòa nhà được gọi là có điện cấp $s$ khi và chỉ khi, sau khi gỡ bỏ bất kỳ một đường dây nào trong khu, tòa nhà đó vẫn nhận được điện từ ít nhất $s$ nhà máy điện. Tìm số lớn nhất có thể của các tòa nhà có điện cấp $s$.
(i) mọi đường dây nối với một nhà máy điện chỉ truyền điện ra khỏi nhà máy đó;
(ii) với mỗi tòa nhà không phải trụ sở chính, tồn tại duy nhất một dãy đường dây tạo thành một lộ trình từ tòa nhà đó đến trụ sở chính.
Một tòa nhà được gọi là có điện cấp $s$ khi và chỉ khi, sau khi gỡ bỏ bất kỳ một đường dây nào trong khu, tòa nhà đó vẫn nhận được điện từ ít nhất $s$ nhà máy điện. Tìm số lớn nhất có thể của các tòa nhà có điện cấp $s$.