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)