Hệ thống trạm phát điện

Một thành phố gồm n khu nhà được đánh số từ 1 đến n. Chính quyền thành phố  muốn lắp đặt hệ thống cung cấp điện sao cho tất cả các khu nhà đều có điện. Để thực hiện việc này, Công ty điện lực thành phố tiến hành khảo sát và đã tính toán được chi phí để nối dây điện giữa các khu nhà với nhau. Cụ thể, để nối khu nhà i với khu nhà j cần một chi phí là C_ij, chi phí này được ghi bằng 0 nếu không thể nối trực tiếp được. Dựa vào bảng chi phí này, hãy chỉ ra phương án cung cấp điện cho thành phố với các yêu cầu sau (thứ tự ưu tiên từ 1):

1.      Tất cả các khu nhà đều có điện.

2.      Các trạm phát điện sẽ đặt tại các khu nhà.

3.      Số lượng trạm phát điện (m) là ít nhất.

4.      Chi phí nối dây (T) là bé nhất (chi phí nối dây là tổng chi phí các đoạn dây giữa các khu nhà theo phương án chọn).

Dữ liệu nhập vào từ tập tin văn bản LUOIDIEN.IN gồm:

-          Dòng đầu chứa số nguyên dương n (n<=100).

-          N dòng tiếp theo, mỗi dòng chứa n số, số ở dòng i cột j chính là C_ij theo mô tả trên.

Kết quả tìm được ghi ra tập tin văn bản LUOIDIEN.OUT. Dòng đầu chứa 2 số m và T. Dòng tiếp theo chứa m số là chỉ số các khu nhà được chọn để đặt trạm phát điện. Các dòng tiếp theo, mỗi dòng chứa n số gồm các số 1 hoặc 0, số ở dòng i cột j cho biết giữa khu nhà i và khu nhà j có được nối với nhau hay không theo phương án bạn đưa ra.

Ghi chú: các số trên cùng dòng cách nhau bởi khoảng trắng.

Ví dụ: