Bài toán Những viên đá quý

Bài toán: Những viên đá quý

Một công ty đồ chơi đá quý chuẩn bị sản xuất một loại trang sức mới được thiết kế dưới dạng một đồ thị dạng cây. Đồ thị dạng cây cho phép từ một đỉnh bất kỳ có thể đi đến tất cả những đỉnh khác thông qua các cạnh mà không tạo thành chu trình. Các đỉnh sẽ được làm từ đá quý và các cạnh là các sợi vàng.
Yêu cầu là những đỉnh kề nhau phải được làm bằng những viên đá quý khác loại nhau. Với mỗi số nguyên p, có chính xác 1 loại đá quý có giá bằng p. Nhiệm vụ của bạn là viết chương trình tính giá trị nhỏ nhất của các viên đá quý cần để làm được loại trang sức trên.
Dữ liệu: Vào từ file gems.inp:
- Dòng đầu là số nguyên N (1<=N<=10000) là số lượng đỉnh.
- N-1 dòng tiếp theo, mỗi dòng gồm 2 số nguyên A và B (1<=A,B<=N, A<>B) cách nhau bởi 1 khoảng trắng, mô tả cạnh nối 2 đỉnh A và B.
Kết quả: Ra file gems.out gồm 1 số nguyên duy nhất là giá trị nhỏ nhất của tổng giá trị các viên đá quý cần dùng.
Ví dụ:
Gems.inp
 
gems.out

8 1 2 3 1 1 4 5 6 1 5 5 7 5 8

11

Thuật toán:
- Nhận xét: Tương tự bài toán tô màu đồ thị, ta thấy, để tô màu cây sao cho 2 đỉnh kề nhau khác màu nhau, ta chỉ cần dùng tối đa 4 màu (4 loại đá quý khác nhau), do đó, ta có thể giải quyết bài toán với 4 loại đá quý có giá trị nhỏ nhất: 1,2,3,4.
- Để sử dụng được phương pháp quy hoạch động, ta cần định hướng cho cây ban đầu: chọn đỉnh 1 làm gốc, dùng DFS xác định quan hệ cha – con giữa các nút trên cây.
- Phương pháp quy hoạch động được áp dụng theo hướng từ các nút lá đến nút gốc, thể hiện qua hàm f[1..n,1..4] với ý nghĩa: f[i,j] là giá trị nhỏ nhất của tổng giá trị các viên đá quý trên cây con gốc i khi nút i được tô màu j. Chỉ có thể tính được f[i,j] khi i là nút lá hoặc các nút con của i đều đã được tính, f[i,j] được tính theo các nút con kề với i.
- Công thức: f[i,j] =
Min(f[i’,k]) (i’ là các nút con kề với i, k=1..4, k<>j)
Download chương trình (gems.pas)

[email protected]