Cấu trúc bảng thưa thớt (Sparse Table)

Tưởng tượng như ta phải xử lý một vấn đề sau:

Cho một mảng A. Thực hiện một số lượng truy vấn như sau:

Mỗi truy vấn gồm 2 số (l, r) (1 <= l, r <= A.length). Hãy tìm:

  • Giá trị (hoặc chỉ số) của phần tử nhỏ nhất trong đoạn [l, r]
  • Giá trị (hoặc chỉ số) của phần tử lớn nhất trong đoạn [l, r]

Như ta đã biết, vấn đề này hoàn toàn có thể xử lý với segment tree, với độ phức tạp thời gian O(N*log(N)) để khởi tạo, O(log(N)) để trả lời truy vấn, và độ phức tạp không gian là O(4*N).

Bài viết này sẽ cung cấp một phương pháp giải khác – sử dụng cấu trúc Sparse Table (bảng thưa thớt – ở đây viết tắt là SpT nhằm phân biệt với ST của segment tree): với độ phức tạp thời gian O(N*log(N)) để khởi tạo, O(1) để trả lời truy vấn, và độ phức tạp không gian là O(N*log(N)).

Khi nào dùng segment tree và khi nào dùng sparse table?

Ta sẽ cân nhắc dựa vào bản chất, yêu cầu bài toán. Thông thường, thao tác cập nhật của segment tree có độ phức tạp O(log(N)) (với 1 phần tử, với một mảng lớn thì thao tác sẽ là O(log(N)) nếu có cài đặt lan truyền lười nhác), còn với sparse table thì độ phức tạp là O(N*log(N)) (cập nhật toàn bộ).

Do đó, sparse table phù hợp với việc biểu diễn dữ liệu “tĩnh” hơn.

Xây dựng SpT từ array

SpT của chúng ta sẽ là một mảng chứa các mảng (không phải mảng 2 chiều, vì kích thước các mảng con không đồng nhất mà sẽ adaptive theo độ dài – trong C++ ta có thể biểu diễn bằng std::vector lồng vào nhau, hoặc để đơn giản cũng có thể sử dụng mảng 2 chiều, chấp nhận chứa các phần tử dư).

Nguyên tắc thực hiện sẽ là: với array A[] ban đầu có kích thước N, mỗi phần tử SpT[i][j] (chỉ số đánh số từ 0) sẽ là giá trị cần thu được trên khoảng [i, i+2^j-1] của A[] (i+2^j-1 < N).

Xét trường hợp đề bài yêu cầu tìm minimum trên khoảng, lúc này ta sẽ có hệ thức:

  • SpT[i][0] = A[i].
  • SpT[i][k] = min(SpT[i][k-1], SpT[i+2^(k-1)][k-1]) (với k > 0).

Các trường hợp khác (sum, max, GCD, etc.) thực hiện tương tự.

Trả lời truy vấn

Tiếp tục xét yêu cầu trả về min.

Ta nhận thấy, với sparse table, giờ đây thay vì so sánh từng phần tử trong vùng cần xét như phương pháp khờ khạo, ta chỉ cần tìm ra 2 giá trị trên sparse table, sao cho hợp vùng biểu diễn của 2 giá trị này đúng bằng vùng biểu diễn của toàn truy vấn (chúng ta sẽ không quan tâm tới giao trong trường hợp min/max/GCD).

Tổng quát hơn, kết quả truy vấn sẽ là giá trị min của SpT[l][j] và SpT[r+1-2^j][j], với j là số tự nhiên lớn nhất thỏa mãn 2^j <= r-l+1. Tức là, ta sẽ so sánh khoảng tiền tố có độ dài 2^j và khoảng hậu tố có độ dài 2^j; và với việc j lớn nhất có thể mà không vượt ra khỏi vùng truy vấn, ta dễ dàng chứng minh được hợp của 2 vùng được xét đúng bằng vùng truy vấn ta cần. Độ phức tạp cho phép so sánh là O(1).

Tuy nhiên, j sẽ được xác định như thế nào?

Nếu phải thử từng giá trị của j, thì sparse table trở nên vô dụng, vì quá trình này đẩy độ phức tạp từ O(1) trở về O(log(N)) như segment tree.

Tuy nhiên, ta có thể giải quyết quá trình này thông qua một bước tiền xử lý nữa.

Gọi Log2[] là array lưu phần nguyên của các giá trị Log2 từ 1 tới N (hiển nhiên, với định nghĩa ở trên, floor(log2(r-l+1)) = Log2[r-l+1] = j. Ta có thể tính toán toàn bộ các giá trị này theo xử lý khờ khạo như trên với độ phức tạp O(N*log(N)) – tức là cũng tương đồng với quá trình khởi tạo sẵn SpT ở trên. Ưu điểm ở đây là, ta sẽ không phải tính lại giá trị này khi xử lý truy vấn.

Mở rộng: Nếu yêu cầu của truy vấn là tìm tổng phần tử trên đoạn?

Lúc này, thay vì so sánh 2 khoảng như ở trên, ta sẽ thực hiện cộng dần từ đầu tới cuối với độ phức tạp O(log(N)): chừng nào l <= r thì cộng thêm vào kết quả một giá trị bằng SpT[l][j], rồi gán lại l := l + 2^j.

Thực ra, với một mảng tĩnh, việc tìm truy vấn tổng sẽ đơn giản hơn nếu ta sử dụng prefix sum, tuy nhiên đây cũng là một phương pháp có thể tham khảo.

 

Bài toán tham khảo 1: SPOJ-RMQSQ

Lời giải: Ideone.com

Bài toán tham khảo 2: VNSPOJ-QMAX

Lời giải: Ideone.com

Bài toán tham khảo 3: VNSPOJ-NKLINEUP

Lời giải: Ideone.com

 

#Akikaze

Featuring #ThuyTrang_12A2

Advertisements

Thư viện code

Code tổng hợp từ các bài viết trên thuytrangcoding, đồng thời với những code do #Team4T viết nhưng chưa đăng trên bài viết nào (do chưa thể viết được chủ đề).

Bài viết có mục đích tổng hợp và tham khảo.

I. Tham lam

1. Bài toán lịch họp (scheduling)

Link bài: PTIT127C – Bố trí phòng họp

Source code: Ideone.com

2. Bài toán tổng chênh lệch tối thiểu (hàm tuyến tính)

Link bài: P187PROI – ROUND 7I – MÁI NHÀ

Source code: Ideone.com

II. Đồ thị

1. Đường đi ngắn nhất

a. Dijkstra

Link bài: Codeforces 20C – Dijkstra?

Source code: Submission 33253245

b. Floyd:

Link bài: CS Academy – Round 70 – Min Distances

Source code: CS Academy – Submission 1370237

2. Cây khung nhỏ nhất

Link bài: VNSPOJ-QBMST

a. Prim: Ideone.com

b. Kruskal: Ideone.com

3. Topological sorting

Link bài: Codeforces 919D – Substring

Source code: Submission 34788171

4. Thành phần liên thông mạnh (SCC)

Link bài: VNSPOJ-TJALG

a. Kosaraju: Ideone.com

b. Tarjan: Ideone.com

III. Cấu trúc dữ liệu

1. Cây tiền tố (Prefix Tree / Trie)

Link bài: P176PROC – ROUND 6C – GOOD OR BAD? (SPOJ – PTIT)

Source code: Ideone.com

2. Cây phân đoạn (Segment Tree)

a. Cơ bản:

Link bài 1: VNSPOJ-QMAX

Source code: Ideone.com

Link bài 2: Codeforces 920F – SUM and REPLACE

Source code: Submission 35221937

b. Lazy Propagation:

Link bài: VNSPOJ-QMAX2

Source code: Ideone.com

IV. Xử lý xâu

1. So khớp chuỗi

Link bài: VNSPOJ-SUBSTR

a. KMP: Ideone.com

b. Z: Ideone.com

c1. Hashing (đơn module): Ideone.com

c2. Hashing (đa module): Ideone.com

2. Hashing

a. Longest Palindromic Substring:

Link bài: VNSPOJ-PALINY

Source code (đơn module): Ideone.com

Source code (đa module): Ideone.com

V. Hình học

1. Bao lồi

Link bài: Kattis Problem – Convex Hull

Source code: Ideone.com

Giải bài toán đường đi ngắn nhất bằng thuật toán Bellman-Ford

Đây là hướng dẫn sử dụng thuật toán Bellman-Ford. Xem thêm:

Thuật toán Bellman-Ford là một trong những thuật toán dùng để tìm đường đi ngắn nhất (chỉ áp dụng cho đồ thị có hướng) từ một điểm tới một điểm nào đó, và mở rộng ra là tìm đường đi ngắn nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều kiện đồ thị không được phép có chu trình âm.

Trước hết, về khâu tổ chức dữ liệu: ta xây dựng một mảng 1D chứa đường đi ngắn nhất giữa đỉnh đang xét tới tất cả các đỉnh còn lại, giá trị ngầm định bằng +INF.

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V).

Ý tưởng thuật toán Bellman-Ford có tính tham lam:

  • Ta thực hiện duyệt V lần, với V là số đỉnh của đồ thị.
  • Với mỗi lần duyệt, ta tìm tất cả các cạnh mà đường đi qua cạnh đó sẽ rút ngắn đường đi ngắn nhất từ đỉnh gốc tới một đỉnh khác.
  • Ở lần duyệt thứ V, nếu còn bất kỳ cạnh nào có thể rút ngắn đường đi, điều đó chứng tỏ đồ thị có chu trình âm, và ta kết thúc thuật toán.

Tính đúng đắn của ý tưởng này được chứng minh quy nạp.

Ta có khẳng định sau: Ở thời điểm mà ta đã đi qua i lần duyệt thì những mệnh đề sau được coi là đúng:

  • Nếu khoảng cách từ điểm gốc tới 1 điểm u không phải là +INF, thì khoảng cách đó đúng bằng độ dài 1 đường đi nào đó từ gốc tới u.
  • Với đỉnh u đó, nếu tồn tại đường đi từ gốc tới u mà đi qua tối đa i cạnh, thì độ dài đường đi ngắn nhất sẽ không vượt quá độ dài đường đi kể trên.

Quá trình chứng minh quy nạp:

  • Trường hợp cơ bản: i = 0. Ta chưa duyệt qua lần nào, nên cả 2 điều đều hiển nhiên đúng (Đường đi ngắn nhất tới đỉnh gốc bằng 0, hiển nhiên vì điểm xuất phát và đích trùng nhau, còn đường đi ngắn nhất tới các đỉnh khác bằng +INF vì ta không có bất kỳ đường đi nào được tìm thấy để tới chúng).
  • Trường hợp quy nạp:
    • Mệnh đề 1 rõ ràng đúng. Ta tưởng tượng, nếu trong quá trình duyệt cạnh, xuất hiện cạnh (u, v) với trọng số w có thể tối ưu hóa đường đi ngắn nhất của v được, thì đương nhiên ta cập nhật độ dài đó: dist[v] = dist[u] + w. Rõ ràng dist[v] là độ dài một đường đi từ gốc tới v, hay chính xác hơn là đường đi từ gốc tới u, rồi đi qua cạnh (u, v) tới v.
    • Với mệnh đề 2, ta tiếp tục sử dụng giả sử về cạnh (u, v) trọng số w như ở trên. Với giả thuyết quy nạp, dist[u] sẽ không vượt quá độ dài bất kỳ đường đi từ gốc tới u mà đi qua tối đa (i-1) cạnh. Do đó, cộng đồng thời 2 vế, ta sẽ có (dist[u] + w_min) không vượt quá độ dài bất kỳ đường đi nào từ gốc tới u với lượng cạnh không quá (i-1), rồi đi qua cạnh (u, v). Hay nói cách khác, không có đường đi nào từ gốc tới v với lượng cạnh không quá i (khớp với giả thuyết quy nạp).

Ta lại nhận thấy, đường đi ngắn nhất hiển nhiên không có chu trình (nên nhớ rằng ta không xét chu trình âm, vì nó sẽ khiến đường đi kéo dài vô tận và độ dài tiến tới -INF, còn nếu chu trình không âm thì việc đi lặp lại chu trình vô nghĩa), vậy nên một đường đi giữa 2 đỉnh sẽ chỉ có tối đa V-1 cạnh.

Vậy nên, thuật toán Bellman-Ford sẽ chỉ cần V lần duyệt cạnh – lần duyệt thứ V sẽ là lần duyệt để kiểm tra chu trình âm: Nếu có đường đi được cập nhật mới ở lần duyệt này, hẳn là đã có 1 đường đi tối ưu nào đó có V cạnh – điều này là vô lý với đồ thị không có chu trình âm.

Độ phức tạp của thuật toán sẽ là O(VE) – khá lớn, nên nếu đồ thị không có cạnh có trọng số âm, thuật toán Dijkstra sẽ là một hướng tiếp cận hữu dụng hơn.

 

Ta xét ví dụ với đồ thị có hướng sau (giả định các đường đi là một chiều, chỉ đi từ đỉnh có số thứ tự thấp hơn tới đỉnh có số thứ tự cao hơn, số có màu đỏ cạnh mỗi đỉnh là độ dài đường đi ngắn nhất từ gốc tới đỉnh đó, và đỉnh gốc là đỉnh 1):

cses-fi-bellmanford1

Thực hiện lần duyệt đầu tiên, ta cập nhật được đường đi ngắn nhất thông qua các cạnh (1, 2); (1, 3); (1, 4):

cses-fi-bellmanford2

Tương tự với lần duyệt thứ 2, cạnh (2, 5) và (3, 4) là các cạnh tối ưu:

cses-fi-bellmanford3

Với lần duyệt thứ 3, chỉ có cạnh (4, 5) cải tiến đường đi tối ưu:

cses-fi-bellmanford4

Tới lần duyệt thứ 4, ta thấy không còn cạnh nào có thể tối ưu hóa bất kỳ đường đi ngắn nhất nào nữa. Tới đây, ta hoàn toàn có thể dừng duyệt (vì chắc chắn việc không còn cạnh có thể tối ưu cũng đồng nghĩa với việc không có chu trình âm trong đồ thị).

 

Ta có thể cài đặt thuật toán như sau:

cses-fi-bellmanford6

Hoặc bạn có thể tham khảo source code của anh Nguyễn Tiến Trung Kiên (kc97ble).

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

 

Giải bài toán đường đi ngắn nhất bằng thuật toán Dijkstra

Đây là hướng dẫn sử dụng thuật toán Dijkstra. Xem thêm:

Thuật toán Dijkstra là một trong những thuật toán cơ bản dùng để tìm đường đi ngắn nhất từ một điểm tới một điểm nào đó, và mở rộng ra là tìm đường đi ngắn nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều kiện các trọng số của đồ thị đó không âm.

Trước hết, về khâu tổ chức dữ liệu: ta xây dựng một mảng 1D chứa đường đi ngắn nhất giữa đỉnh đang xét tới tất cả các đỉnh còn lại, giá trị ngầm định bằng +INF.

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V).

Ta xét đồ thị vô hướng sau (số màu đỏ là đường đi ngắn nhất xuất phát từ đỉnh 1 tới đỉnh được xét):
cses-fi-dijkstra1

Quá trình thực hiện thuật toán Dijkstra sẽ diễn ra như sau:

  • Chọn một điểm bất kỳ chưa được duyệt và có đường đi ngắn nhất từ điểm gốc tới nó là nhỏ nhất.
  • Từ điểm đó, loang đường đi ra tất cả các đỉnh kề cận, và cập nhật lại đường đi ngắn nhất tới các đỉnh đó nếu đường đi mới tối ưu hơn.
  • Nếu còn điểm chưa được duyệt (hoặc chưa tìm được điểm đích, tùy yêu cầu đề bài), ta trở lại bước 1.

Ta sẽ phân tích tuần tự theo nền tảng ý tưởng này:

Đầu tiên, ta xét đỉnh 1 (vì đường đi ngắn nhất từ 1 tới 1 hiển nhiên có độ dài 0).

Sau quá trình cập nhật, ta có các giá trị đường đi ngắn nhất mới: cses-fi-dijkstra2

Tiếp theo, ta duyệt đỉnh 5 (đường đi ngắn nhất từ 1 tới 5 có độ dài 1).

Sau cập nhật, ta thu được các giá trị mới:

cses-fi-dijkstra3

Tiếp theo, ta duyệt đỉnh 4 (đường đi ngắn nhất từ 1 tới 4 có độ dài 3).

Sau cập nhật, ta thu được các giá trị mới:

cses-fi-dijkstra4

Cứ tiếp tục như vậy cho tới khi duyệt hết đỉnh, ta sẽ thu được các giá trị hoàn chỉnh:

cses-fi-dijkstra5.png

Sở dĩ phương pháp tham lam này đúng bởi, ta đã ngầm định đặt ra điều kiện trước: các trọng số của các cạnh phải là các số không âm. Do đó, việc duyệt liên tục từ các đỉnh có độ dài đường đi ngắn nhất là cực tiểu sẽ luôn được đảm bảo tính chính xác: ta không thể xuất phát từ bất kỳ đỉnh nào khác qua một giá trị trung gian mà thu được đường đi nhỏ nhất từ đỉnh gốc tới đỉnh cực tiểu ta đang xét thậm chí còn nhỏ hơn nữa được.

Tuy nhiên, với trường hợp trọng số âm, lập luận này bị bác bỏ. Xét đồ thị sau:

cses-fi-dijkstra6.png

Bằng mắt thường, ta có thể thấy rằng: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 4 sẽ là đoạn đường 1->3->4.

Tuy nhiên, áp dụng tư duy thuật toán Dijkstra, ta có:

  • Khởi tạo: s_path[1] = 0, s_path[2] = INF, s_path[3] = INF, s_path[4] = INF.
  • Xuất phát từ đỉnh 1. Cập nhật: s_path[2] = 2, s_path[3] = 6.
  • Xuất phát từ đỉnh 2. Cập nhật: s_path[4] = 5.
  • Xuất phát từ đỉnh 4. Do đây là đỉnh đích nên ngừng thuật toán, kết luận ans = 5.

Rõ ràng, do phương pháp tham lam không tính đến trường hợp độ dài đường đi nhỏ nhất có thể giảm, nên nhánh xuất phát từ đỉnh 3 bị loại bỏ, dẫn đến kết quả sai.

 

Một phép cài đặt thuật toán Dijkstra thành công được quyết định chủ yếu bởi độ phức tạp của quá trình tìm đỉnh tiếp theo được duyệt.

Với phương pháp khờ khạo, độ phức tạp của quá trình này sẽ là O(V), do đó độ phức tạp của thuật toán trở thành O(V^2).

Ta có thể cải tiến quá trình này thông qua hàng đợi ưu tiên – giúp độ phức tạp của quá trình tìm kiếm đỉnh chỉ biến thiên theo hàm logarithm.

Một ví dụ về việc cài đặt như sau:

cses-fi-dijkstra7

Ta nhận thấy, trong cách cài đặt này, trong hàng đợi sẽ chứa độ dài cạnh với giá trị âm. Sở dĩ vậy là bởi, priority_queue của C++ sẽ ngầm định trả về giá trị lớn nhất ở đầu hàng đợi, mà ta lại cần giá trị nhỏ nhất. Tất nhiên, ta có nhiều cách khác để xử lý, như thay đổi toán tử so sánh cho priority_queue, sử dụng STL set/multiset, v.v. …

Độ phức tạp cho cách cài đặt trên là O(E+V*log V).

 

Bài toán tham khảo: Codeforces 20C – Dijkstra?

Tóm tắt đề bài:

Cho 1 đồ thị vô hướng có trọng số gồm N đỉnh và M cạnh. Hãy tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh N.

Nếu không có đường đi, in ra -1.

Nếu có nhiều đường đi cùng trả về 1 giá trị tối ưu, có thể tùy chọn đường đi.

Phương pháp:

Đây là một bài tập căn bản cho thuật toán Dijkstra. Có một số điểm cần lưu ý:

  • Output sẽ trả về -1 nếu sau khi kết thúc duyệt, đường đi ngắn nhất từ 1 tới N là +INF (nhớ rằng đề bài không đảm bảo đồ thị là liên thông).
  • Vì ta phải in ra đường đi nên ngoài việc xác định giá trị đường đi nhỏ nhất, ta còn phải thực hiện truy vết. Phương pháp truy vết thì vẫn tương tự như khi duyệt DFS/BFS thông thường.

Lời giải (của D.Bách): Submission 33253245

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

 

Giải bài toán đường đi ngắn nhất bằng thuật toán Floyd-Warshall

Đây là hướng dẫn sử dụng thuật toán Floyd-Warshall. Xem thêm:

Trong những bài toán đường đi ngắn nhất mà chúng ta cần thông tin về đường đi giữa nhiều cặp đỉnh, ta có xu hướng là sẽ tính toán đường đi ngắn nhất giữa mọi cặp đỉnh.

Thuật toán Floyd-Warshall là một thuật toán phù hợp để thực hiện tác vụ này.

Trước hết, ta cần phải nắm về khâu tổ chức dữ liệu: đường đi ngắn nhất giữa 2 đỉnh bất kỳ sẽ được lưu trong một mảng 2 chiều, ngầm định sẽ có giá trị là +INF nếu không có đường nối trực tiếp giữa chúng, hoặc nếu có đường nối thì giá trị ban đầu sẽ là trọng số của đường nối đó. Các tính toán sau này sẽ là so sánh giữa đường đi ngắn nhất hiện tại với một đường đi trung gian (giả sử, với 2 đỉnh A và B, ta so sánh đường đi ngắn nhất hiện thời giữa 2 đỉnh này với tổng độ dài đường đi ngắn nhất từ A và từ B tới 1 đỉnh C trung gian nào đó).

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V^2).

Ta xét đồ thị vô hướng sau: cses-fi-floyd1

Từ quy tắc trên, mảng 2D chứa đường đi ngắn nhất ban đầu sẽ được khởi tạo như sau:

cses-fi-floyd2

Từ đây, quá trình thực hiện thuật toán Floyd-Warshall sẽ diễn ra như sau:

  • Chọn lần lượt từng đỉnh của đồ thị làm đỉnh trung gian (ta quy ước là C).
    • Chọn một cặp 2 đỉnh phân biệt và không trùng với đỉnh trung gian (ta quy ước lần lượt là A và B).
      • Thực hiện so sánh như ở trên: đường đi ngắn nhất giữa A và B sẽ bằng giá trị nhỏ nhất của:
        • Giá trị đường đi ngắn nhất hiện thời giữa A và B.
        • Tổng của giá trị đường đi ngắn nhất hiện thời giữa A và C, và đường đi ngắn nhất hiện thời giữa B và C.

Ta sẽ phân tích tuần tự theo nền tảng ý tưởng này:

Đầu tiên, C = 1. Nhờ đỉnh 1 làm trung gian, ta thấy xuất hiện đường đi từ đỉnh 2 tới đỉnh 4 (độ dài 14), và từ đỉnh 2 tới đỉnh 5 (độ dài 6).

Đường đi trung gian qua đỉnh 1 để đi từ đỉnh 4 tới đỉnh 5 không tối ưu về chiều dài (9 + 1 > 2) nên ta không cập nhật lại đường đi ngắn nhất giữa 2 đỉnh 4 và 5.

Mảng 2D lúc này trở thành: cses-fi-floyd3.png

Tiếp theo, ta duyệt tới C = 2.

Đường đi từ 3 tới 1 (độ dài 7), từ 3 tới 5 (độ dài 8) được hình thành.

Đường đi từ 3 tới 4 không cập nhật độ dài (7 < 2 + 5 + 9).

Mảng 2D lúc này là: cses-fi-floyd4.png

Cứ tiếp tục lựa chọn C như vậy cho tới hết, ta sẽ thu được mảng 2D hoàn chỉnh:

cses-fi-floyd5.png

Giả sử, qua mảng này, ta thấy đường đi ngắn nhất từ đỉnh 2 tới đỉnh 4 có độ dài 8. Dựa theo đồ thị thì nó là đoạn đường sau: cses-fi-floyd6

 

Quá trình cài đặt thuật toán Floyd-Warshall khá đơn giản, có thể chia làm 2 công đoạn:

  1. Khởi tạo mảng 2D chứa đường đi ngắn nhất (ở code này thì đồ thị được biểu diễn ở dạng ma trận kề, và distance là tên mảng): cses-fi-floyd7
  2. Tính toán giá trị đường đi ngắn nhất: cses-fi-floyd8

Hoàn toàn dễ dàng nhận ra, thuật toán có độ phức tạp O(V^3). Do đó, thuật toán chỉ nên áp dụng với những đồ thị có số đỉnh nhỏ (thường chỉ tới 100-200 đỉnh).

 

Bài toán tham khảo: CS Academy – Round 70 – Min Distances

Tóm tắt đề bài:

Cho 2 số N và M, và M bộ 3 số (a, b, c).

Hãy tạo ra một đồ thị đơn vô hướng, liên thông, có trọng số với N đỉnh, sao cho với mỗi bộ số (a, b, c) đề cập ở trên, đường đi ngắn nhất giữa đỉnh a và đỉnh b phải bằng c.

Mọi cạnh trên đồ thị được in ra có trọng số không quá 10^7.

Nếu không có đồ thị thỏa mãn, in ra -1.

Phương pháp:

Trường hợp duy nhất để không tìm thấy đồ thị thỏa mãn là các cạnh bị ràng buộc chồng chéo lên nhau – theo cách mà 2 cạnh ràng buộc trung gian có độ dài ngắn hơn một cạnh ràng buộc khác.

Ta nhận thấy, ta hoàn toàn có thể lập một đồ thị đầy đủ, với trọng số tất cả các cạnh bằng 10^7. Với mỗi bộ số (a, b, c), ta gán lại trọng số của cạnh (a, b) bằng c.

Như vậy, ít nhất nếu không tính các đường đi gián tiếp, đồ thị ta lập ra vẫn thỏa mãn ràng buộc của đề bài.

Tới đây, ta có thể sử dụng thuật toán Floyd để tìm đường đi ngắn nhất của tất cả các cặp đỉnh trên đồ thị.

Nếu không có bộ số (a, b, c) nào mà đường đi ngắn nhất từ a tới b khác c, thì đồ thị đó là thỏa mãn, và có thể in ra.

Ngược lại, in ra -1.

Lời giải (của neko_nyaa): CS Academy – Submission 1372996

Lời giải (của D.Bách): CS Academy – Submission 1370237

 

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

 

Bài toán đường đi ngắn nhất

Khái niệm căn bản nhất về loại bài toán này là: với một đồ thị đã cho, ta cần tìm một đường đi giữa 2 đỉnh sao cho độ dài đường đi (tức là tổng trọng số các cạnh trên đường đi đó) là nhỏ nhất có thể.

Có 2 biến thể phổ biến nhất cho dạng bài toán này, đó là:

  1. Cố định trước 1 đỉnh, tìm đường đi ngắn nhất từ đỉnh đó tới 1 đỉnh khác bất kỳ.
  2. Cho trước đồ thị, yêu cầu tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trên đồ thị đó.

Trong thực tế, có rất nhiều thuật toán được ứng dụng cho loại bài toán này:

  1. Tìm đường đi ngắn nhất từ 1 đỉnh cố định:
    • Đối với đồ thị vô hướng:
      • Nếu không có trọng số, hiển nhiên ta sẽ dùng phương pháp duyệt BFS.
      • Nếu có trọng số, ta có thể dùng thuật toán Dijkstra.
        • Độ phức tạp: tùy theo phương thức lưu trữ, thường thấy là O(V^2), O((E + V) log V), O(E + V log V).
    • Với đồ thị có hướng không chu trình (DAG), việc tìm kiếm có thể dễ dàng thực hiện thông qua sắp xếp tô-pô (topological sorting).
      • Độ phức tạp: O(V + E).
    • Với đồ thị có hướng thông thường, trọng số không âm, ngoài việc áp dụng Dijkstra, ta còn có thể dùng thuật toán Bellman-Ford.
      • Độ phức tạp: O(VE)
      • Trong trường hợp một số cạnh có trọng số âm nhưng không có chu trình âm thì ta cũng có thể sử dụng Bellman-Ford.
  2. Tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ: Ta sử dụng thuật toán Floyd-Warshall.
    • Độ phức tạp: O(V*f(V,E)), với f(V,E) là độ phức tạp của thuật toán ở mục 1.
    • Nếu sử dụng đúng phương pháp của Floyd-Warshall (không kết hợp các phương pháp ở mục 1 với việc chọn 1 đỉnh làm đỉnh cố định) thì độ phức tạp là O(V^3).

 

#ThuyTrang_12A2

Tìm thành phần liên thông mạnh của đồ thị có hướng bằng thuật toán Tarjan

Đây là hướng dẫn sử dụng thuật toán Tarjan. Đối với phương pháp giải sử dụng thuật toán Kosaraju, xem tại đây.

Trước hết, khái niệm “thành phần liên thông mạnh” (Strongly Connected Components – SCC) được định nghĩa là một tập hợp các đỉnh trên đồ thị có hướng mà từ 1 đỉnh, ta có thể đi đến tất cả các đỉnh còn lại trong tập hợp đó. Ngoài ra, mỗi TPLTM phải là cực đại, nghĩa là không thể thêm bất cứ đỉnh nào vào một TPLTM mà vẫn tạo thành TPLTM.

 

Dĩ nhiên, việc tìm TPLTM của đồ thị có hướng không dễ dàng như tìm TPLT của đồ thị vô hướng. Ví dụ với đồ thị có dạng giản lược sau: (0) -> (1) -> (2) -> (3) – nếu ta tìm TPLTM theo cách của đồ thị vô hướng, thì nếu giả định ta xuất phát từ bất kỳ đỉnh nào không phải (0), thì ta không thể đi tới đỉnh (0) được – tức là kết quả TPLTM tìm được thay đổi theo đỉnh (và thậm chí cũng không chính xác).

 

Chúng ta sẽ tiến tới một cách tiếp cận khác cho bài toán TPLTM – thuật toán Tarjan.

Ý tưởng của thuật toán này dựa trên phương pháp duyệt theo chiều sâu (depth-first search | DFS).

Đầu tiên, ta tạo sẵn một ngăn xếp (stack) – nó có nhiệm vụ lưu trữ các phần tử đang nằm cùng một thành phần liên thông mạnh chưa hoàn chỉnh (tức là vẫn còn có thể có những phần tử khác thuộc chung TPLTM).

Với mỗi đỉnh trên đồ thị, ta lưu 2 thuộc tính: “Enum” dùng để xác định thứ tự được duyệt của đỉnh đó (dựa theo DFS) và “Lowest” dùng để xác định thứ tự nhỏ nhất có thể của đỉnh có thể được đi tới từ đỉnh đó.

Việc xử lý các thuộc tính này trong quá trình DFS diễn ra như sau:

  • Trước hết, mỗi khi bắt đầu duyệt một đỉnh, giá trị Enum được gán cố định cho đỉnh đó, và sẽ không đổi trong suốt quá trình. Quy tắc của chúng ta vẫn sẽ là, đỉnh được duyệt trước sẽ có giá trị Enum nhỏ hơn.
  • Hiển nhiên, cho tới lúc này Lowest đúng bằng Enum.
  • Đặt chỉ số của đỉnh đang xét lên đầu stack.
  • Xem xét các đỉnh có thể được đi tới từ đỉnh đang xét:
    • Nếu đỉnh đó đã được duyệt qua (Enum khác giá trị đặt ngầm định) thì hiệu chỉnh giá trị Lowest theo giá trị Lowest của đỉnh đó (chỉ thực hiện khi giá trị đó nhỏ hơn giá trị hiện tại).
    • Nếu chưa được duyệt thì ta thực hiện duyệt đỉnh đó (như bất kỳ một hàm DFS đệ quy thông thường nào), rồi sau đó hiệu chỉnh giá trị Lowest theo quy tắc tương tự ở trên.
  • Sau khi kết thúc duyệt một đỉnh, ta kiểm tra Lowest và Enum:
    • Nếu 2 giá trị khác nhau, tức đây không phải đỉnh “gốc” của một TPLTM nào, ta bỏ qua và kết thúc hàm tại đỉnh đó.
    • Ngược lại, tức là ta đã trở về gốc của TPLTM, hay nói cách khác toàn bộ các khả năng duyệt đã được kiểm tra. Tới đây, ta có thể xóa tất cả các đỉnh khỏi stack và đồng thời loại bỏ khỏi việc bị duyệt lại (cách đơn giản nhất là đặt Enum và Lowest tới giá trị dương vô cùng).

Độ phức tạp của thuật toán là O(V+E) (chỉ cần 1 lần DFS trên toàn bộ đồ thị).

 

Bài toán 1: VNSPOJ-TJALG

Lời giải 1 (của Ngọc Mai): Ideone.com

Lời giải 2 (của Nguyễn Tiến Trung Kiên – kc97ble, NUS): kc97ble

 

Bài toán 2: Codeforces 427C – Checkposts

Tóm tắt bài toán: Cho một đồ thị có hướng gồm n đỉnh, m cạnh. Mỗi đỉnh i có một giá trị v(i) cố định. Hãy chọn tập hợp các đỉnh sao cho mỗi đỉnh đại diện cho một TPLTM, và tổng giá trị của các đỉnh được chọn là nhỏ nhất. Đồng thời, cho biết có bao nhiêu cách chọn tập đỉnh thỏa mãn? (2 cách khác nhau khi có bất kỳ 1 phần tử nào khác nhau, đáp số lấy dư khi chia cho 10^9+7).

Phương pháp: Ta sẽ liệt kê tất cả các TPLTM của đồ thị, và với mỗi TPLTM chọn ra 1 giá trị nhỏ nhất. Tổng các giá trị này sẽ là số đầu tiên của output.

Số thứ 2 của output sẽ được tính theo cách: với mỗi TPLTM, ta tìm xem có bao nhiêu đỉnh có giá trị bằng với giá trị min cho TPLTM đó – số cần tìm là tích số lần xuất hiện ở mỗi TPLTM (chú ý chia dư).

Lời giải (của D.Bách): Submission 35816808

 

#ThuyTrang_12A2