Tẩu thoát (1 dạng QHĐ nữa này)

[ngtrhieu0011]

TẨU THOÁT
Sau khi xuất sắc hoàn thành nhiệm vụ, góp phần giải cứu các con tin đang bị một nhóm khủng bố bắt giữ, điệp viên AT001 bị truy sát khắp nơi. Để cắt đuôi các thế lực thù địch, AT001 lên kế hoạch tẩu thoát như sau: trong nhiều ngày (k ngày) anh sẽ bay từ thành phố này sang thành phố khác (có n thành phố), mỗi ngày một chuyến bay. Cuối cùng, anh sẽ bay đến Washington để nhận nhiệm vụ mới.
Vì ngân sách hạn hẹp, AT001 muốn thục hiện hành trình tẩu thoát ít tốn chi phí nhất. Điều này không dễ dàng vì giá vé máy bay và các chuyến bay giữa các thành phố thì khác nhau trong từng ngày. Mỗi 2 thành phố có một lịch bay nhất định và lịch này được lập lại theo một chu kỳ. Các chu kỳ này khác nhau giữa các cặp thành phố. Bạn hãy viết một chương trình giúp AT001 thục hiện cuộc tẩu thoát này.
INPUT
Tập tin input gồm nhiều test, mỗi test bắt đầu bằng một dòng chứa 2 số nguyên n, k, (2 ≤ n ≤ 10 và ; 1 ≤ k ≤ 100) trong đó n là số thành phố mà AT001 có thể đến, k là số lượng chuyến bay mà anh sẽ thực hiện. Các thành phố được đánh số từ 1..n, với 1 là Kabul (Afghanistan) và n là Washington (Mỹ), đích đến cuối cùng của anh.
Tiếp theo bạn sẽ được cho biết thông tin của n(n-1) lịch bay, mỗi lịch bay giữa 2 thành phố được mô tả trên một dòng . N-1 lịch bay đầu tiên sẽ tương ứng với các chuyến bay từ thành phố 1 đến các thành phố còn lại (lần lượt là 2, 3,…, n). Mô tả tương tự cho các lịch bay tiếp theo.
Thông tin cho một lịch bay bắt dầu bằng số nguyên d, chu kỳ của lịch bay (1 ≤ d ≤ 30). Tiếp đó là d số nguyên dương, là giá vé của các chuyến bay giữa hai thành phố trong các ngày 1, 2, 3,..,d. Giá vé là 0 cho biết không có chuyến bay giữa hai thành phố trong ngày đó.
Ví dụ, Nếu thông tin lịch bay là “3 80 0 70” cho biết chu kỳ của lịch bay là 3 ngày, ngày đầu chuyến bay có giá 80, ngày thứ hai không có chuyến bay, ngày thứ ba giá vé là 70. Sau 3 ngày chu kỳ lập lại nên ngày thứ tư chuyến bay có giá vé là 80, không có chuyến bay trong ngày thú 5, v…v.
Tập tin Input kết thúc khi n=k=0.
OUTPUT
Với mỗi bộ Test trong Input, hãy xuất ra số thứ tự của Test. Nếu có thể sắp lịch bay cho AT001 trong k ngày, bắt đầu từ thành phố 1, và cuối cùng (sau k ngày) đến thành phố n, (lưu ý: ở ngày thứ i, 1 ≤ i < k, AT001 có thể bay đến thành phố j bất kì, với điều kiện ngày thứ i có chuyến bay đến thành phố j) thì hãy xuất “Chi phi toi thieu la x”, với x là chi phí tối thiểu cho hành trình của AT001. Nếu không thể sắp được lịch bay cho AT001 với điều kiện như trên, hãy xuất “Khong the sap lich bay”.
Xuất một dòng trắng giữa các Test.

Input Mẫu
3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0

Ouput tương ứng
Chi phi toi thieu la 460.
Khong the sap lich bay.

[bld]

thanks a hieu trước đã, e sẽ bổ sung bài viết sau , cháy túi rồi

[ngtrhieu0011]

đúng là QHĐ... giá vé cũng "động" ^^

[bld]

F[n,i,j] là chi phí ngắn nhất đi đến thành phố j , liền trước là thành phố i , ngày thứ n
F[0,i,j]=0;
F[n,0,j]=F[n,j,0]=-1
F[n,i,i]=0;

F[n,i,j]= min(F[n-1,1..n,i]) + chi phí đi từ i->j ngày k
{phải đảm bảo khác -1 nữa ^^)
tìm max của F[k,.,n] truy vết

[=========> Bổ sung bài viết <=========]

em làm thế , có sai thì báo đề e nghĩ lại , đừng sửa liền nha !thanks

[ngtrhieu0011]

tốn dữ liệu nhiều quá, với lại mảng 3 chiều thì độ phức tạp thuật toán O(n*m*k) là hàm mũ 3 không bảo đảm thời gian chạy kịp ^^

[bld]

vậy thì cần sắp xếp , 1 cái gì đó ..., e cảm giác như vậy , không biết có đúng ko nữa
đề e suy nghĩ ...

[=========> Bổ sung bài viết <=========]

hay thật , giải xong bài này mở mang đầu óc

[=========> Bổ sung bài viết <=========]

đây nhé a hiếu : hi vọng không sai

à , cái đoạn đề ko rõ chỗ , có phải bắt buộc khởi hành từ tp 1 hay không, nếu có thì ở dưới , ko thì báo để e sửa lại 1 chút)

gọi F[j,i] là chi phí thấp nhất đi qua đỉnh cuối là đỉnh i, tại ngày thứ j
cơ sở
F[1,i]=chi phí đi ngày thứ nhất từ tp 1 đến tp i;(cái này là bắt buộc)
F[j,i]=min( F[j-1,m] + chi phí đi ngày thứ j từ tp m -> tp i, m:1..n , m<>i )
có thể cài đặt bài này = 2 mảng 1 chiều


for i:=1 to n do F1[i]:=c[1,i,1]{chi phí đi từ 1 đến i, ngày thứ 1}
ngay:=1;
repeat
fillchar(F2,sizeof(F2),max);
inc(ngay)
for i:=1 to n do
for j:=1 to n do
if j<>i then
if F1[j]+c[j,i,ngay] <F2[i] then F2[i]:=c[j,i,ngay]+F1[j];
F1:=F2;
until ngay=k;

sai thì sửa ^^

[ngtrhieu0011]

yes, ý tưởng đứng gòy ^^

[quangtq]

Pro QHĐ có khác. Không có ý tưởng của 2 người chắc ko bao giờ làm được mất.

[bld]

nhưng mà ko chắc ròi a hieu ,làm như vậy không chừng lúc truy vết có vài tp thăm đến mấy lần , phải đánh dấu , kiểu nào đây ...

[linhhahaduc]

Mình QHĐ như thế này !
f[i,j] là chi phí nhỏ nhất để đến đc thành phố i và đã dùng j ngày
khởi gán f[...,...] = vô cùng ; f[1,0]:=0;
Hàm QHĐ sẽ là
f[i,j] :=min ( f[t,j-c[t,i,ngay]] + c[t,i,tien] ) với t chạy từ 0 --> n
và để truy vết thì làm thêm 1 mảng trace[i,j] với trace[i,j] chính = t thỏa mãn :D
Độ phức tạp N*N*k
p/s : Mình giải thích hơi khó hiểu , mong mọi người thông cảm :d

[quangtq]

Dễ hiểu thôi mà. Thấy giải thuật vậy thì mình cũng làm được.

[linhhahaduc]

Thử làm 1 bài QHĐ như thế này nhé , đề cũng như trên nhưng thêm là phải đi tất cả n thành phố rồi mới đc về wasington :D . Khó phết :(

[ngtrhieu0011]

chu trình halminton, như vậy càng dễ

[bld]

@duc : vậy phải sửa lại đề là n+1=k
cũng đặt F[i,j] nhưng làm n+1 lần , đỉnh xuất phát bắt buộc là 1 nên vẫn tạo cơ sở như bài trên, sau đó ,mỗi khi tính 1 ô của bảng ví dụ F[i,j] tức ngày i , tp j , ta phải lưu tại ô đó 1 dãy nhị phân độ dài n đề đánh dấu các đỉnh trên lộ trình ngắn nhất đến tpj trong i ngày , khi tính 1 ô F[i,j] nào đó ta phải đảm bảo lộ trình đến ô đi trước phải không chứa tp j và tp j đó ko phải là washington , tức ta chỉ tính F[i,j] với j>=2, đến hàng thứ n+1 của bảng , tính F[k,1]
@ a hieu : làm như vậy rắc rối hơn chứ .

[linhhahaduc]

Chu trình hamilton bạn làm = Độ phức tạp bao nhiêu :)) . :D bài này mình làm Độ phức tạp O(1 shl n * n * k) :D

[bld]

e ko biết tính thế nào nhưng ra thế này
K*(1+2+3+4...+N) :D bậy bạ nhỉ

[linhhahaduc]

:O thuật toán gì mà khủng vật vã vậy

[quangtq]

Khủng gì O(K*(1+..+n)) nghĩa là O(K*max(1,2,..,n)) theo định nghĩa O mà
<=> worst: O(k*n) and best: O(K)
Chưa hiểu sâu òy

[linhhahaduc]

KO Ý MÌNH LÀ khủng vì độ phức tạp nhỏ chứ ko fai cái công thức =)) BLD thử trình bày cách đó xem nào :D

[quangtq]

Lạ nhỉ. Post thuật toán lên đi bld.
Bài này mình chỉ biết mỗi cách Hamilton

[bld]

mình đã trình bày ở trang 1 rồi

[linhhahaduc]

Đấy là bài đầu chứ . Ý mình là post thuật toán để giải thay cách = Hamilton cơ
:D

[bld]

ko , em giải bài này = QHD (đã trình bày ở trang trước , nhưng ko phải bài giải của bài tẩu thoát , khác) , vì tính bắt buộc của nó ,chỉ cần đánh dấu lại theo kiểu xâu nhị phân là có thể thành hamilton được .

[linhhahaduc]

uh đúng rồi , cách này chuẩn đây . Mới lớp 9 mà đã biết QGĐ Trạng thái :-s khủng thật

[quangtq]

Pro mà. Mình mơ chưa tới.
=========================

[linhhahaduc]

phải mơ tới chứ . Cố lên :))

[quangtq]

QHĐ luôn là phần em kém nhất. Hỏi sao quay lui, đệ quy hay Floyd/Dijkstra mình hiểu thấy rất dễ. Nhưng QHĐ thì chịu. Tìm được công thức truy hồi rất khó.