Bài viết sưu tầm

Bảo tồn động vật hoang dã

(Nguồn bài: thầy Lê Minh Hoàng)

Một khu bảo tồn  động vật có N  địa  điểm và các  đường  đi hai chiều nối các  địa điểm đó, địa điểm thứ i có nhiệt độ là t_i, giữa hai địa  điểm bất kỳ có nhiều nhất là một đường đi nối chúng.

Người ta  muốn  di  chuyển  một  loài  động  vật  quý  hiếm từ  địa  điểm  A tới  địa điểm  B, tuy  nhiên  nếu  chênh  lệch  về nhiệt  độ  giữa hai  địa  điểm  liên tiếp trên đường đi là quá cao thì loài động vật này rất có thể bị chết.

Yêu cầu: Hãy chỉ ra một hành trình mà độ lệch nhiệt độ lớn nhất giữa hai địa điểm liên tiếp bất kỳ trên đường đi là cực tiểu.

Dữ liệu vào: Đọc từ file MOVE.INP

- Dòng 1: Chứa ba số N, A, B (2 ≤ N ≤ 200; A ¹B)

- Dòng 2: Chứa N số tự nhiên t₁, t₂, ..., t_N ("i: 0 ≤ t_i ≤ 20000)

- Các dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v cho biết giữa hai địa điểm u và v có đường đi nối chúng.

Kết quả: Ghi ra file MOVE.OUT ghi một số nguyên là độ lệch nhiệt độ lớn nhất giữa hai  địa  điểm liên tiếp bất kỳ trên đường đi tìm được, nếu không tồn tại đường đi thì dòng này ghi số -1.

Các số trên một dòng của Input/ Output file được ghi cách nhau một dấu cách

Ví dụ:

Hướng dẫn:

Bài toán yêu cầu tìm một hành trình  đi từ A tới B sao cho  độ lệch nhiệt độ lớn nhất  Res  giữa hai  địa  điểm liên tiếp bất kỳ trên  đường  đi là nhỏ nhất. Gọi  MaxT là giá trị nhiệt  độ  t_i lớn nhất, vậy  Res  nằm trong [0..MaxT].  Ứng với mỗi giá trị chặt nhị phân ta dùng thuật toán tìm kiếm theo chiều rộng kiểm tra xem có đường đi từ A tới B không.

Function BFS(Val: Integer): Boolean;

Var u, v: Integer;

Begin

InitBFS;

Repeat

u := Pop;

For v := 1 To n Do

If a[u,v]and (Trace[v]=0) and (Abs(t[u]-t[v])<=Val) Then

Begin

Trace[v] := u;

If v = B Then EXIT(True);

Push(v);

End;

Until First > Last;

BFS := False;

End;

Đoạn chương trình chặt nhị phân tìm Res

Procedure Solve;

Var D, C, G: Integer;

Begin

Res:=-1;

D:= -1; C:= maxT + 1;

While D < C do

Begin

G := (D + C) div 2;

if BFS(G) Then

Begin

Res:=G;

C:= G-1;

End

Else D:=G+1;

End;

End;

Độ phức tạp là O(N².Log MaxT)