SPOJ.COM – Thuật toán bài PIZZALOC - Pizza Location
Đề bài:
Picko muốn mở một số cửa hàng pizza tại 1 số địa điểm. Bánh pizza sẽ cung cấp cho mọi khách hàng nằm trong hình tròn bán kính R với tâm là các địa điểm được chọn.
Xác định số khách hàng lớn nhất có thể phục vụ.
Input
Dòng đầu là hai số K, R : số nhà hàng có thể được mở và bán kính phục vụ của mỗi nhà hàng,1 ≤ K ≤ 10, 1 ≤ R ≤ 500.
Dòng thứ hai là M, số địa điểm có thể đặt nhà hàng, K ≤ M ≤ 20.
M dòng tiếp theo, mỗi dòng là 2 số nguyên X và Y, -1000 ≤ X,Y ≤ 1000.
Dòng tiếp theo là N, số khu nhà, 1 ≤ N ≤ 100.
Mỗi dòng trong N dòng tiếp theo là 3 số nguyên X, Y , S, là tọa độ và số người ở khu nhà đó, -1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100.
Khu nhà nằm trong bán kính của nhà hàng nếu khoảng cách giữa chúng <= R. Không có 2 khu nhà tại cùng 1 địa điểm.
Output
Ghi ra số người tối đa có thể được phục vụ.
Ví dụ:
pizza.in
2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1
pizza.out
18
pizza.in
2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2
pizza.out
12
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/PIZZALOC/vn/
Phân tích:
-
Trong bài toán này, ta sẽ phải xây K nhà hàng trong M vị trí. Ở đây, thực chất là ta sẽ phải liệt kê ra tổ hợp chập K của M phần tử trường hợp.
-
Với mỗi trường hợp, ta sẽ kiểm tra xem mỗi ngôi nhà có được phục vụ bởi nhà hàng nào hay không.
-
Tôi sẽ triển khai bài toán sử dụng thuật toán quay lui có điều kiện - Backtracking.
-
Một điều chú ý là: với mỗi vị trí có thể đặt nhà hàng, tôi sẽ kiểm tra xem tại vị trí đó, nếu như tôi đặt nhà hàng thì nó sẽ phục vụ được cho những ngôi nhà nào. Kết quả tôi sẽ lưu được vào một mảng. Điều này sẽ tránh bị time limit.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include<iostream> | |
| using namespace std; | |
| const int MAX_PLACE = 21; | |
| const int MAX_HOUSE = 101; | |
| int NumRest, R; // Số lượng nhà hàng và bán kính | |
| int NumPlac; // Số địa điểm có thể đặt nhà hàng | |
| int XPlace[MAX_PLACE], YPlace[MAX_PLACE]; // Toạ độ các điểm có thể đặt nhà hàng | |
| int NumHous; // Số khu nhà | |
| int XHouse[MAX_HOUSE], YHouse[MAX_HOUSE]; // Toạ độ các khu nhà | |
| int NumPeop[MAX_HOUSE]; // Số người ở mỗi khu nhà | |
| int MaxPeop; // Số người tối đa có thể phục vụ | |
| int SumPeop; // Tổng số người | |
| int PRest[MAX_PLACE]; // Lưu lại vị trí đã đặt của các nhà hàng | |
| int Reach[MAX_PLACE][MAX_HOUSE]; // Kiểm tra xem một vị trí có thể phục vụ những ngôi nhà nào | |
| int Count[MAX_PLACE]; // Đếm số nhà mà nhà hàng có thể phục vụ ứng với mỗi vị trí | |
| /* | |
| * @PARAM: pos : lưu vị trí đang xét | |
| * @PARAM: numIgnore : số vị trí ko đặt | |
| * @PARAM: numRestor : số nhà hàng đã đặt | |
| */ | |
| void Check(int pos, int numIgnore, int numRestor) | |
| { | |
| if(pos == NumPlac) | |
| { | |
| // Kiểm tra với những cách đã đặt cách nào phục vụ nhiều người nhất | |
| // Duyệt lần lượt các ngôi nhà, xem với mỗi ngôi nhà nó có được phục vụ không | |
| // Những người được phục vụ | |
| int SerPeop = 0; | |
| int Mark[MAX_HOUSE] = {0}; | |
| for(int j = 0; j < NumRest; j++) | |
| { | |
| int idRest = PRest[j]; | |
| for(int i = 0; i < Count[idRest]; i++) | |
| { | |
| // Chú ý: mỗi ngôi nhà chỉ được tính một lần. | |
| int idHouse = Reach[idRest][i]; | |
| if(Mark[idHouse] == 0) | |
| { | |
| SerPeop += NumPeop[idHouse]; | |
| Mark[idHouse] = 1; | |
| } | |
| // Nếu đã phục vụ được tối đa rồi thì thoát luôn | |
| if(SerPeop == SumPeop) break; | |
| } | |
| } | |
| if(SerPeop > MaxPeop) MaxPeop = SerPeop; | |
| return; | |
| } | |
| if(MaxPeop == SumPeop) return; | |
| // Đặt nhà hàng | |
| if(numRestor < NumRest) | |
| { | |
| PRest[numRestor] = pos; | |
| Check(pos + 1, numIgnore, numRestor + 1); | |
| if(MaxPeop == SumPeop) return; | |
| } | |
| // Ko đặt nhà hàng | |
| if(numIgnore < NumPlac - NumRest) | |
| Check(pos + 1, numIgnore + 1, numRestor); | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); | |
| freopen("input.txt","r",stdin); | |
| cin >> NumRest >> R >> NumPlac; | |
| for(int i = 0; i < NumPlac; i++) | |
| cin >> XPlace[i] >> YPlace[i]; | |
| SumPeop = MaxPeop = 0; | |
| cin >> NumHous; | |
| for(int i = 0; i < NumHous; i++) | |
| { | |
| cin >> XHouse[i] >> YHouse[i] >> NumPeop[i]; | |
| SumPeop += NumPeop[i]; | |
| Count[i] = 0; | |
| } | |
| // Lưu lại những ngôi nhà mà tại mỗi vị trí, nhà hàng có thể phục vụ | |
| for(int j = 0; j < NumPlac; j++) | |
| for(int i = 0; i < NumHous; i++) | |
| { | |
| int temp = (XHouse[i] - XPlace[j])*(XHouse[i] - XPlace[j]) + | |
| (YHouse[i] - YPlace[j])*(YHouse[i] - YPlace[j]); | |
| if(temp <= R*R) Reach[j][Count[j]++] = i; | |
| } | |
| // Đặt NumRest nhà hàng trong NumPlac vị trí | |
| Check(0, 0, 0); | |
| cout << MaxPeop << endl; | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.