1 số bài tập Pascal thi HSG (Chu trình - đồ thị)

Các bài toán với chu trình đồ thị

Nguyễn Văn Trung
ứng dụng của chu trình trong đồ thị hiện chưa được xét nhiều. Tôi xin đưa ra một số các bài toán tương đối hay, khó sử dụng tính chất của chu trình mà đem lại cài đặt hết sức đơn giản so với các thuật giải khác và có phần hiệu quả hơn rất nhiều. Định nghĩa: Trong một đồ thị có hướng, độ dài của một chu trình của đồ thị là số đỉnh thuộc chu trình đó. Bài toán 1: Đồng hồ cổ Trong một ngôi mộ cổ, các nhà khoa học đã tìm thấy một thiết bị đặc biệt, trên đó có N nút, mỗi nút khắc một kí tự đặc biệt, ấn vào nút đặc biệt dưới đế, thiết bị bắt đầu hoạt động! Sau mỗi ngày, vị trí các kí tự lại thay đổi. Kết quả quan sát cho thấy, sau mỗi khoảng thời gian cố định, kí tự ở vị trí i sẽ chuyển tới vị trí j và mỗi i có một j cố định của mình. Dĩ nhiên, ở mỗi vị trí chỉ có một ký tự. Ngừơi ta dự đoán đây là lịch đếm ngày phục vụ cho một công việc nào đó, ví dụ để xác định thời gian luyện dưựơc liệu điều chế các biệt dựơc bí ẩn hoặc tính tuổi của một người...Số khoảng thời gian từ khi bấm nút khởi động đến lúc tất cả các ký tự quay trở về vị trí ban đầu của nó đưựơc gọi là chu kỳ của hoạt động, hay ngắn gọn là chu kỳ. Hãy lập trình xác định chu kỳ của thiết bị tìm thấy, biết rằng không có chu kỳ nào vựơt quá 1012. Dữ liệu: vào từ file văn bản CLOCK.INP: - Dòng đầu tiên chứa số nguyên N - số ký tự trên thiết bị (1 <= n <= 10000). - Các dòng sau chứa N số nguyên A1, A2,..., An cho biết ký tự ở vị trí i sẽ chuyển tới vị trí Ai sau một khoảng thời gian. Các số cách nhau ít nhất một dấu cách. Kết quả: Ra file văn bản CLOCK.OUT số nguyên - chu kỳ của thiết bị Ví dụ:
Thuật toán : 1. Đánh số các ký tự từ 1 đến N tương ứng với N đỉnh của đồ thị. 2. Sau một khoảng thời gian kí tự i sẽ chuyển tới vị trí A[i], ta coi như đỉnh thứ i của đồ thị có cạnh nối đến đỉnh A[i], ta được một đồ thị có hướng gồm N đỉnh, một cung sẽ nối từ kí tự đến kí tự tiếp theo nó biến đổi thành. 3. Gọi t[i] = thời gian để kí tự thứ i chuyển về vị trí ban đầu. Xuất phát từ đỉnh i của đồ thị dễ nhận thấy từ i chỉ có một đường đi duy nhất để quay trở về i, đường đi đó chính là chu trình chứa i do đó t[i] = độ dài chu trình chứa đỉnh i. 4. Dùng mảng đánh dấu free[i] = true nếu chưa tìm được chu trình chứa đỉnh i, false nếu ngược lại. Đoạn mã sau tìm t[i] với i = 1…n; procedure findt; var i, j, nt : Integer; {nt là biến cho biết độ dài của chu trình đang xét} begin FillChar(Free, SizeOf(Free), True); for i := 1 to n do if Free[i] then begin nt := 0; j := i; {bắt đầu tìm chu trình xuất phát từ đỉnh i} repeat Free[j] := False; Inc(nt); j := A[j]; until j = i; repeat t[j] := nt; {các đỉnh thuộc chu trình đều có thời gian biến đổi là nt } j := A[j]; until j = i; end ; end ; Ta xét tiếp bài toán : Như vậy ta đã biết sau một khoảng thời gian t[i] thì ký tự ở vị trí i sẽ về vị trí ban đầu, hiển nhiên sau một khoảng thời gian là BS(t[i]) { bội số của t[i]} thì i cũng sẽ trở về vị trí ban đầu. Vậy thời gian nhỏ nhất để các ký tự đều trở về vị trí ban đầu là BCNN(t[i]) i = 1..n. Bài toán đưa về bài toán cơ bản là tìm BCNN của các số cho trước. Đến đây vấn đề đã được giải quyết ổn thoả, ta có thể bỏ qua bước còn lại của bài toán. Bài toán 2: Tập các lá bài cực đại: Cho n lá bài ( n ≤ 20000) được đánh số hiệu từ 1 đến N. Trên mỗi lá bài ghi một số nguyên F[i], (1 ≤ F[i] ≤ n, i = 1..n), có thể có nhiều