Thuật toán nhánh cận Tôi đang cần gấp 3 ví dụ có sử dụng thuật toán nhánh cận (trừ các bài người đưa hàng, balo trong sách giáo khoa). Bạn nào có thì gửi cho mình nhé, mình cám ơn rất rất nhiều. Mình cũng có mấy bài muốn các bạn giải dùm. {b}1.Bài toán bầu cử{/b} Mộ{b}{/b}t uỷ ban bầu cử cần tìm k vị trí đặt thùng phiếu trong một khu vực dân cư gồm n địa điểm đánh số từ 1 đến n. Mỗi thùng phiếu cần đặt tại một trong số n địa điểm dân cư. Có m tuyến đường giao thông (đánh số từ 1 đến m), mỗi tuyến nối một cặp địa điểm dân cư nào đó. Cần tìm k địa điểm đặt thùng phiếu sao cho tổng độ dài đường đi của các cử tri (mỗi cử tri đi bỏ phiếu ở nơi đặt thùng phiếu gần địa điểm mình ở nhất) là nhỏ nhất. Dữ liệu vào cho trong file INPUT có cấu trúc: - Dòng đầu tiên ghi ba số n,k,m; - Dòng thứ hai ghi các số nguyên dương C[1] .C[n] (C là số cử tri ở địa điểm thứ i). - M dòng tiếp theo mỗi dòng chứa 3 số nguyên dương u[j],v[j],d[j] theo thứ tự là điểm đầu, điểm cuối và độ dài của tuyến đường j. Kết quả ghi ra file OUTPUT dưới dạng: - Dòng đầu tiên ghi tổng độ dài đường đi của tất cả các cử tri. - Dòng tiếp theo ghi k số p[1],p[2],...,p[k] là các vị trí đặt thùng phiếu. {b}2.Bài toán hình vuông la tinh{/b} Định nghĩa bài toán : Hình vuông la tinh cấp n (n ? 26) là ma trận vuông kích thước n x n mà mỗi dòng và mỗi cột của nó đều là một hoán bị của n chữ cái đầu tiên trong dãy chữ A, B, ?. , Z. Hai hình vuông la tinh được gọi là tương đương nếu từ hình này ta có thể thu được hình kia nhờ sử dụng các phép biến đổi sau : 1) đổi chỗ hai dòng 2) đổ chỗ hai cột 3) đổi tên hai chữ cái Bài toán đặt ra là : Xác định xem hai hình vuông cho trước có tương đương hay không ? Diễn tả vào ra : Input : Cho Ω1 ,Ω2 là 2 hình vuông la tinh cấp n Output : Xác định 2 hai hình vuông trên có tương đương hay không Ví dụ: Hai hình vuông la tinh A B C D A B C D 1 = B D A C 2 = B C D A C A D B C D A B D C B A D A B C là tương đương, bởi vì đổi chỗ dòng 3 và 4 của 1 ta thu được A B C D B D A C D C B A C A D B tiếp đến đổi chỗ cột 3 và 4 ta thu được A B D C B D C A D C A B C A B D cuối cùng, đổi tên hai chữ C và D cho nhau (nghĩa là thay C bởi D và thay D bởi C) ta thu được 2.
