Kỳ thi chọn học sinh giỏi THPT cấp Quốc gia môn Tin học

(Bản scan)

Bài 3. Kế hoạch cải tô (7 điểm)
Mạng giao thông của thành phố NB có m nút giao thông và m đoạn đường phố hai chiều nối các
nút giao thông. Các nút giao thông được đánh số từ 1 đến ø. Các đoạn đường phố được đánh số từ
1 đến m. Mạng giao thông của thành phố có tỉnh chất sau đây:
Giữa hai nút giao thông bất kỳ có không quá một đoạn đường phố nói chúng;
Không có đoạn đường phố nào nỗi một nút giao thông với chính nó.
Vấn đề giao thông là thách thức với chính quyển thành phố từ nhiễu năm. Với mong muốn đảm
bảo việc đi lại thuận lợi hơn cho người dân, chính quyền thành phố quyết định tiến hành cải tổ
mạng giao thông, trước hết nhằm đảm bảo có thể đi từ một nút giao thông bất kỳ đến tất cả các nút
còn lại. (Lưu ý là mạng giao thông trước khi cải tô có thể không đảm bảo yêu cầu này.) Tuy nhiên,
do hạn hẹp về nguồn kinh phí, trước mắt kế hoạch cải tổ chỉ có thể bao gồm 2 công việc:
Loại bỏ một đoạn đường phố hiện có khỏi mạng giao thông;
Xây dựng một đoạn đường chưa từng có trước đó nỗi hai nút giao thông khác nhau.
Đông thời, sau khi thực hiện cải tổ, mạng giao thông phải đảm bảo có thể đi từ một nút giao thông
bắt kỳ đến tất cả các nút còn lại. `