Nhốt bò ! Hix !

[Teak]

Bài toán nghe khá đơn giản, dễ hiểu :
Có n con bò được nhốt trong n chuồng bò (mỗi con 1 chuồng, tất nhiên). Nhưng trong đó lại có các cặp bò là bạn của nhau nên chúng muốn được nhốt gần nhau. Yêu cầu là tìm cách nhốt các con bò sao cho tổng khoảng cách cua các con bò bạn nhau là ít nhất. Hix, khoảng cách của 2 con bò bạn nhau là trị tuyệt đối của hiệu của 2 số chuồng nhốt 2 con bò đó.
Input : dòng đầu là n số con bò và F số cặp bạn bè
F dòng sau mỗi dòng chứa 2 số là số của 2 con bạn nhau, nếu đã có 2 con a b rồi thì sẽ không cần ghi lại b a. Hiểu chứ ạh ?
Output: In ra tổng khoảng cách ít nhất
VD
1/ Input
6 5
1 2
1 3
2 6
3 5
5 6
Output
8
* Giải thích : 5 3 1 2 6
2/ Input
11 11
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
4 10
Output
31
* Giải thích : 9 7 10 4 2 1 3 5 6 8 11
Không đệ quy nghe, đệ quy em làm roài chạy không nổi , hix hix . Help Help !

[Junior IT]

Giới hạn của N là bao nhiêu ?

[Teak]

Hà, wen mất. N<=30, F<=4*N !
Hix, cố gắng giùm nha anh em !

[Junior IT]

Bài này là NP-hard
Chỉ có thể giải bằng BFS hoặc A*. Ý tưởng theo A* :
- Trạng thái bắt đầu là chưa có con bò nào được xếp vào chuồng
- Lặp :
+ Chọn trạng thái tốt nhất trong các trạng thái chưa xét, nếu trạng thái vừa chọn tất cả các con bò đều có chuồng rồi => thóat, đó là kết quả
+ Nếu trạng thái vừa chọn chưa xếp hết số bò, thì xếp lần lượt vào các chuồng => sinh ra trạng thái tiếp theo, loại bỏ những trạng thái chắc chắn ko xét đến nữa

Trạng thái tốt nhất tức là tổng khỏang cách nhỏ nhất
Việc chọn trạng thái tốt nhất dùng Heap, và kiểm tra trạng thái đã xét hay chưa dùng Hash table

[Teak]

Cái em cần là thuật toán tối ưu kìa anh, làm ơn chỉ rõ ra đi, hix hix. Có rất nhiều thuật toán đã áp dụng nhưng không đi đến lời giải đúng. Hix Anh nói rõ hơn ý tưởng của anh nghe ! Hix !

[Junior IT]

Lời giải mình nói ở trên là tối ưu :)

[Teak]

Chưa biết đò thị làm sao làm hả anh ? Hix