Sau đây mình xin trình bày một số bài toán có sử dụng truy vấn trên đồ thị
Bài toán 1: Cho n đỉnh, và n-1 giai đoạn. Giai đoạn i cho
phép ta liên kết đỉnh i+1 à với 1 đỉnh nào đấy(<i) . Ban đầu có đỉnh 1.
Bài toán đặt ra: Với mỗi giai đoạn, hãy tìm khoảng cách xa nhất giữa 2 đinh bất
kì.
// Không hiểu đề các bạn
có thể tìm bài C1, và C2 để đọc J
Bài toán trên được xử
lí hoàn toàn trên cây, nên thông thường việc sử dụng BIT hoặc IT khá khó khăn.
Bây giờ ta giả sử hai
đỉnh khoảng cách xa nhất trước giai đoạn i+1 là (u,v)
Bây giờ khi ta thêm i
và cây, nếu khoảng cách max thay đổi thì i sẽ thế chỗ u hoặc v
int d1=dis(v,i), d2=dis(u,i);
if(d1>d2){if(res<d1){res=d1;u=i;}}
else{
if(res<d2){res=d2;v=i;}
}
Và vấn đề bây giờ ta cần
tìm khoảng cách giũa 2 đỉnh trên cây nhanh nhất có thể. Như sau
int dis(int u,int v){return lvl[u]+ lvl[v]-2*lvl[lca(u,v)];}
với lvll[u] là độ xâu
của nút u
Ví dụ như hình trên ta
có : lvl[1] = 1 , lvl[2] = lvl[3] =2 , lvl[4] = lvl[5]= lvl[6] = 3
Bài toán 2:DHSERV
Do giới hạn n khá nhỏ
( n <= 500) cho nên với mỗi lần thực hiện thao tác (1) nếu x chưa được “bật”
trước đó, ta sẽ cập nhật khoảng cách ngắn nhất của x đến các đỉnh khác. Ta thực
hiện được điều này nhờ thuật toán Floyd .
Bài toán 3: Jtree
Ta dễ ràng nhận thấy
công thức qhđ: F[i] là chi phí nhỏ nhất đi từ đỉnh i à 1
Và với mỗi chiếc vé được
bán ở đỉnh i có thể đi tối đa k chuyến và có giá là w. ta có công thức qhđ như
sau:
F[i] = max (F[i] ,
F[j] + w ) ( dis(i,j) <= k và j là tổ tiên của i) .Độ phức của hàm lấy max
bây giờ là khá lớn, tuy nhiên ta có thể giảm xuống còn O(log) nhờ RMQ :D .
Vậy là bài toán đã được
giải quyết
Một số bài toán truy vấn khác:
Không có nhận xét nào:
Đăng nhận xét