[VOJ]TPJOUR

[Lê Tuệ]

Bài toán chia làm hai phần:
Xét 1 tập hợp S các đỉnh có nhãn nhỏ hơn hoặc bằng k. Gọi f[S,i,d] là
số cách đi qua ‘len’ cạnh và dừng lại tại đỉnh i, trên đường đi chỉ đi
qua các đỉnh thuộc S hoặc các đỉnh có nhãn lớn hơn k. Dễ thấy:
f[S,i,len]=∑f[S,j,len-1] với mọi đỉnh j có đường đi tới i, và j thuộc
S hoặc j lớn hơn k.
Do giá trị của d là rất lớn nên ta phải tính f bằng phương pháp nhân
ma trận.
Sau khi tính được f[S,i,d], ta tính g[S,i] tức là số cách đi qua d
cạnh và đi hết tất cả các đỉnh thuộc tập S và không đi vào các đỉnh có
nhãn nhỏ hơn hoặc bằng k không thuộc S và dừng lại tại i.
Để dễ hiểu ta xét ví dụ: tập S gồm các đỉnh {1,3,5}
Xét các tập con của S: {rỗng} {1} {3} {5} {1,3} {1,5} {3,5}
Ta thấy các đường đi đi qua các đỉnh nào đó thuộc S gồm các loại đường
đi sau:
- Không đi qua đỉnh nào thuộc S
- Chỉ đi qua đỉnh 1, không đi qua đỉnh 3,5
- Chỉ đi qua đỉnh 3, không đi qua đỉnh 1,5
- Chỉ đi qua đỉnh 5, không đi qua đỉnh 1,3
- Chỉ đi qua đỉnh 1,3, không đi qua đỉnh 5
- Chỉ đi qua đỉnh 1,5 không đi qua đỉnh 3
- Chỉ đi qua đỉnh 3,5 không đi qua đỉnh 1
- Đi qua cả 3 đỉnh 1,3,5
Như vậy g[{1,3,5},i]=f[{1,3,5},i,d]-g[{rỗng}]-g[{1},i]-g[{3},i]-
g[{5},i]-g[{1,3},i]-g[{1,5},i]-g[{3,5},i]
Kết quả của bài toàn sẽ là: ∑g[{1,2,…,k},i,d] với 1<=i<=n.
Bài này time limit rất chặt, phải có một số biện pháp để tăng tốc
chương trình.

[Lê Tuệ]

PS: Độ phức tạp thuật toán là: Tính F: O(2^K*N^3*log(d)). Tính G:
O(2^K*2^K)