Đề - Đáp án Tin học 10 - Bài 2 - Olympic 30/4/2012 - Xây dựng hệ thống lưới điện

Công ty truyền tải điện ABC đang thực hiện dự án cung cấp cho một số xã vùng cao của một huyện miền núi. Dự án đã thực hiện được giai đoạn 1, cty đã xây dựng dc N trạm biến áp đặt tại N địa điểm trên địa bàn. Các trạm biến áp này dc đánh số từ 1 đến N (2 <=N<=600). Hiện nay cty tiếp tục thực hiện giai đoạn 2 là cần nối N-1 đường dây điện giữa các trạm biến áp này sao cho khi một trạm biến áp bất kỳ dc nối với lưới điện quốc gia thì tất cả các trạm đều dc cung cấp điện. Hiện tại giữa các trạm biến áp này đã có M (N<=M<=2000) con đường bộ để từ trạm biến áp này có thể đi đến bất kỳ trạm biến áp khác và các hộ dân đều đang sống trên con đường này. Để nối đường dây giữa 2 trạm khác nhau, trạm thứ i với trạm thứ j thì có thể cung cấp dc điện sinh hoạt cho C[i,j] (0<=C[i,j]<=1000) hộ gia đình sống dọc theo con đường này.
Yêu cầu: Tính cách nối dây để cung cấp điện sinh hoạt cho nhiều hộ nhất.
Ví dụ:

ELECTRIC.INP	ELECTRIC.OUT
3 3 1 2 9 1 3 6 2 3 7	16

Lời giải:
C[i,j]:=-C[i,j]. Áp dụng Kruskal.