NỘI DUNG
TỔNG QUAN
Tìm đường đi giữa hai đỉnh bất kỳ trên đồ thị là một bài toán cơ bản nhưng có vai trò quan trọng trong lý thuyết đồ thị, vì nhiều vấn đề liên quan đến đồ thị đều bắt nguồn từ bài toán này Chúng ta sẽ xem xét một bài toán cụ thể để minh họa cho điều này.
Cho một đồ thị ( G) ban đầu đồ thị này rỗng Bài toán yêu cầu thực hiện q truy vấn có dạng i ,u , v :
Nếu i=1 thêm cạnh ( u , v ) ; ( v , u) và đồ thị (G )
Nếu i=2 trả lời hai đỉnh u , v có đường đi đến nhau hay không?
Truy vấn i=1 thường có độ phức tạp O(1), được coi là tối ưu Ngược lại, truy vấn i=2 liên quan đến việc tìm đường đi giữa hai đỉnh u và v, là một bài toán cơ bản trong lý thuyết đồ thị Để giải quyết bài toán này, chúng ta có thể áp dụng hai thuật toán là DFS (Depth-first search) và BFS (Breadth-first search), cả hai đều có độ phức tạp O(n), với n là số đỉnh của đồ thị.
Sử dụng thuật toán DFS hoặc BFS có độ phức tạp O(q n), điều này khiến chúng không khả thi cho các trường hợp với q và n lớn Do đó, cần cải tiến thuật toán để giảm độ phức tạp xuống còn O(q log(n)) hoặc O(q).
Trong phần tiếp theo của chuyên đề, tôi sẽ trình bày cấu trúc dữ liệu Disjoint – Set – Union (DSU) thực hiện bài toán này với độ phức tạp
Trong khoa học máy tính, Cấu trúc dữ liệu Disjoint-Set Union (DSU) là một công cụ quản lý các phần tử được chia thành các tập con không giao nhau DSU hỗ trợ các phép toán như thêm tập con mới, kết hợp các tập con và kiểm tra xem các phần tử có thuộc cùng một tập hợp hay không.
Cấu trúc dữ liệu Disjoint – Set - Union có nhiều ứng dụng trong các thuật toán đồ thị đặc biệt là thuật toán Kruskal để tìm cây khung nhỏ nhất
1.3 Các phép toán cơ bản
Make_set(v): Tạo ra một tập hợp mới để chứa phần tử mới v.
Union_set(a, b): Hợp nhất hai tập hợp (tập hợp chứa phần tử a và tập hợp chứa phần tử b).
Hàm Find_set(v) trả về phần tử đại diện của tập hợp chứa phần tử v Phần tử đại diện này được xác định cho mỗi tập hợp và có thể thay đổi sau các phép toán Union_set Nó được sử dụng để kiểm tra xem hai phần tử có thuộc cùng một tập hợp hay không.
1.4 Cài đặt DSU hiệu quả với cấu trúc cây
Chúng ta sẽ tổ chức các tập hợp thành rừng cây, trong đó mỗi cây đại diện cho một tập hợp cụ thể Gốc của mỗi cây sẽ là phần tử đại diện cho tập hợp đó.
Hình dưới đây minh họa một cách tạo cây
Đầu tiên, mỗi phần tử được thiết lập thành một cây với phần tử đó làm gốc Tiếp theo, chúng ta kết hợp cây chứa đỉnh 1 và cây chứa đỉnh 2 thành cây gốc 1, sau đó kết hợp cây chứa đỉnh 3 với cây chứa đỉnh 4 thành cây gốc 3 Cuối cùng, cây gốc 1 được kết hợp với cây gốc 3 để tạo thành cây gốc 1 Để thực hiện điều này, chúng ta có thể sử dụng phương pháp cài đặt đơn giản với hàm void make_set(int v) { parent[v] = v; }.
} int find_set(int v) { if (v == parent[v]) return v; return find_set(parent[v]);
} void union_sets(int a, int b) { a = find_set(a); b = find_set(b); if (a != b) parent[b] = a;
Cách cài đặt hiện tại không hiệu quả, đặc biệt khi cây suy biến thành chuỗi dài, dẫn đến độ phức tạp O(n) cho hàm find_set(v) Để cải thiện hiệu suất, tôi sẽ giới thiệu hai phương pháp tối ưu, trong đó có tối ưu hóa bằng phương pháp nén lộ trình.
Bước tối ưu này nhằm tăng tốc hàm find_set() bằng cách tìm gốc p cho tất cả các đỉnh trên đường đi giữa đỉnh v và p Mục tiêu của bước nén lộ trình là rút ngắn các đường đi của các node, bằng cách thiết lập cha của mỗi đỉnh đã được thăm trực tiếp là p.
Hình 2 minh họa quá trình nén lộ trình khi thực hiện hàm Find_set(7) Bên trái là cấu trúc cây ban đầu, trong khi bên phải thể hiện việc nén lộ trình, giúp rút ngắn đường đi đến các đỉnh.
Sau đây là cài đặt mới của hàm Find_set(): int find_set(int v) { if (v == parent[v]) return v; return parent[v] = find_set(parent[v]);
Hàm này bắt đầu bằng việc xác định gốc p của v, sau đó gán gốc trực tiếp của các đỉnh trên đường đi từ v đến p là p theo kiểu stack Cải tiến đơn giản này giúp giảm độ phức tạp trung bình của hàm Find_set() xuống O(log n) Đồng thời, tối ưu hóa hàm Union_set bằng cách sử dụng kích thước hoặc thứ hạng cũng mang lại hiệu quả cao.
Trong phần này, chúng ta sẽ tối ưu hàm Union_set() bằng cách xác định cây nào nên gắn vào cây nào Cách cài đặt đơn giản trước đó luôn gắn cây hai vào cây một, nhưng điều này có thể dẫn đến việc cây trở thành một chuỗi có độ dài O(n) Do đó, trong bước cài đặt tối ưu này, chúng ta sẽ lựa chọn cẩn thận cây nào cần ghép vào cây nào để cải thiện hiệu suất.
Có nhiều phương pháp thích nghi (heuristics) có thể áp dụng, nhưng hai cách tiếp cận phổ biến nhất là sử dụng kích thước của cây (rank) và chiều sâu của cây (size).
Cách thực hiện của hàm Union_set() dựa trên size của cây: void make_set(int v) { parent[v] = v; size[v] = 1;
} void union_set(int a, int b) { a = find_set(a); b = find_set(b); if (a != b) { if (size[a] < size[b]) swap(a, b); parent[b] = a; size[a] += size[b];
Cách thực hiện của hàm Union_set() dựa trên chiều sâu của cây: void make_set(int v) { parent[v] = v; rank[v] = 0;
} void union_set(int a, int b) { a = find_set(a); b = find_set(b); if (a != b) { if (rank[a] < rank[b]) swap(a, b); parent[b] = a; if (rank[a] == rank[b]) rank[a]++;
Cả hai cách cài đặt này yêu cầu bộ nhớ và độ phức tạp là tương đương vì vậy khi cài đặt dùng một trong hai đều được.
Khi kết hợp hai giải pháp tối ưu là nén lộ trình và hợp nhất theo size/rank, chúng ta có thể đạt được độ phức tạp hằng số cho mỗi truy vấn Độ phức tạp của mỗi truy vấn được chứng minh là O(α(n)), trong đó α(n) hầu như không vượt quá 4 với các giá trị n thích hợp (n ≤ 10^600).
1.5 Áp dụng DSU giải bài toán (*)
Như đã trình bày ở mục 1.1.1 bài toán (*) được giải với độ phức tạp
O (q log( n)) là một giải pháp chưa tối ưu Sau đây tôi sẽ trình bày thuật toán kết hợp với DSU để giảm độ phức tạp của bài toán.
Với truy vấn i=1 dùng hàm ¿ set ( ) với cách cài hợp bởi size
Sử dụng truy vấn i=2 với hàm Find set() và áp dụng kỹ thuật nén lộ trình, thuật toán đạt được độ phức tạp O(q α(n)) Sự kết hợp của hai kỹ thuật này mang lại hiệu quả tối ưu cho quá trình xử lý.
ỨNG DỤNG CỦA DSU
2.1 Xác định và quản lý các thành phần liên thông của đồ thị Đây là một trong những ứng dụng phổ biến nhất của DSU Thông thường bài toán được định nghĩa như nhau: Ban đầu chúng ta có một đồ thị rỗng, chúng ta phải thêm các đỉnh và các cạnh vô hướng và trả lời các truy vấn có dạng (a , b ) -“các đỉnh a và b có cùng thành phần liên thông hay không?”
2.2 Xác định các thành phần liên thông trong một bức ảnh
Bài toán yêu cầu xác định kích thước của các thành phần liên thông trong một bức ảnh kích thước n × m điểm ảnh, chỉ sử dụng hai màu trắng và đen Các thành phần liên thông là những vùng ảnh có điểm ảnh màu đen Việc phân tích này giúp hiểu rõ cấu trúc và phân bố của các vùng màu đen trong bức ảnh.
Thuật toán xử lý các điểm ảnh đen bằng cách kiểm tra 4 điểm lân cận của mỗi điểm ảnh Nếu lân cận cũng là điểm ảnh đen, hàm Union_set() sẽ được gọi để kết nối chúng Qua đó, chúng ta tạo ra một cấu trúc DSU với n.m nút tương ứng với các điểm ảnh Kết quả cuối cùng là một rừng cây của DSU, trong đó mỗi cây đại diện cho một thành phần liên thông rời rạc.
2.3 Nén bước nhảy trên một đoạn/Tô màu các dãy con offline
Bài toán đặt ra là tìm kiếm điểm cuối cùng trên đường đi từ một đỉnh bất kỳ trong một tập hợp các đỉnh, mỗi đỉnh kết nối với một đỉnh khác Sử dụng cấu trúc dữ liệu DSU, chúng ta có thể xác định điểm cuối này chỉ trong thời gian hằng số thông qua tất cả các cạnh.
Một ví dụ cho ứng dụng của bài toán này là tô màu cho các dãy con Chúng ta có một dãy có độ dài L, ban đầu tất cả các phần tử được tô màu 0 Với mỗi truy vấn (l, r, c), ta sẽ tô lại màu cho đoạn con [l; r] thành màu c Sau q truy vấn, nhiệm vụ của chúng ta là xác định màu cuối cùng của mỗi phần tử trong dãy.
Để tạo DSU, mỗi phần tử sẽ liên kết với một phần tử khác chưa được tô màu, bắt đầu với việc mỗi phần tử liên kết với chính nó Khi một đoạn được tô màu, tất cả các ô trong đoạn đó sẽ được liên kết với ô ngay sau đoạn đó.
Để giải quyết bài toán này, chúng ta cần đảo ngược các truy vấn từ cuối đến đầu Với mỗi truy vấn (l, r, c), chỉ cần tô màu các ô trong đoạn [l, r] chưa được tô màu, vì tất cả các ô đã được tô màu đều mang màu cuối cùng của chúng Để tối ưu hóa việc lặp lại trên các ô chưa được tô màu, chúng ta sử dụng cấu trúc dữ liệu DSU Chúng ta cũng cần tìm ô bên trái nhất trong đoạn.
[ l, r] chưa được tô màu và tô màu cho nó Với con trỏ, chúng ta di chuyển ô trống kề tiếp sang bên phải.
Ở đây chúng ta có thể dùng DSU với nén lộ trình (path compression) nhưng chúng ta không thể dùng Union by rank/size.
Do đó, độ phức tạp sẽ là O( log (n)) cho mỗi Union_set
Cài đặt: for (int i = 0; i = 0; i ) { int l = query[i].l; int r = query[i].r; int c = query[i].c; for (int v = find_set(l); v |T| thì ghép T vào S, X không bị di chuyển.
Nếu |S| = 2 * |S|.
Như vậy sau mỗi bước di chuyển, tập hợp chứa X lớn hơn ít nhất gấp đôi tập cũ Vậy X không thể bị di chuyển quá log2(N) lần.
Để tối ưu hóa hiệu quả của thuật toán, việc lưu trữ danh sách kề sao cho mỗi phần tử chỉ xuất hiện một lần là rất quan trọng STL Set là một lựa chọn dễ sử dụng, nhưng chi phí di chuyển một phần tử sẽ là O(log2(N)) Nếu bạn có kỹ năng lập trình tốt và tự tin, có thể sử dụng bảng băm hoặc Trie để giảm chi phí thêm và xóa phần tử xuống O(1).
Chương trình, test chấm: https://www.dropbox.com/sh/o5unxwd62o6zvh4/AAAiXpSZNl7wpHGoobi34Wara?dl=0
Tái cơ cấu trúc
Ngay cả những công ty thành công nhất cũng có thể đối mặt với khủng hoảng khi cần đưa ra quyết định khó khăn như tái cơ cấu, loại bỏ hoặc hợp nhất các phòng ban Mô hình của một công ty trong giai đoạn này thường cho thấy những thách thức mà họ phải vượt qua.
Trong một công ty phần mềm lớn, có n nhân viên, mỗi người thuộc về một phòng ban cụ thể Ban đầu, mỗi nhân viên đảm nhận một dự án riêng và làm việc trong phòng của mình, với n phòng ban tương ứng, mỗi phòng chỉ có một người.
Trong bối cảnh khó khăn, công ty đã quyết định thuê một người quản lý khủng hoảng để cải thiện quy trình làm việc và nâng cao hiệu quả Người quản lý này sẽ xây dựng một đội ngũ làm việc chung, từ đó có thể đưa ra các quyết định cần thiết để vượt qua thách thức.
Khi nhập phòng của đội chứa nhân viên x với phòng của đội chứa nhân viên y, sẽ tạo thành một phòng lớn hơn với tổng số nhân viên là tổng số nhân viên của cả hai phòng Tuy nhiên, nếu đội chứa nhân viên x và đội chứa nhân viên y là một, thì sẽ không có bất kỳ thay đổi nào xảy ra.
Nhập tất cả các đội chứa nhan viên x , đội chứa nhân viên x +1 , , đội chứa nhân viên y thành một đội lớn hơn Ở đây x và y (
1 ≤ x ≤ y ≤ n ) là số hiệu của hai nhân viên nào đó. Đôi khi người quản lý khủng hoảng tự hỏi xem hai nhân viên x và y (
1 ≤ x , y ≤ n ) có cùng một đội hay không?
Viết chương trình giúp người quản lý khủng hoảng thực hiện các điều trên.
Dòng đầu tiên chứa hai số nguyên n , q (1 ≤n ≤ 2∙ 10 5 ; 1≤ q ≤ 5 ∙10 5 ¿ là số nhân viên và số thao tác mà người quản lý khủng hoảng thực hiện.
Trong đoạn tiếp theo, mỗi dòng sẽ mô tả một thao tác với ba số type, x, y, trong đó type có thể là 1, 2 hoặc 3 Nếu type bằng 1 hoặc 2, thao tác sẽ đưa ra quyết định thuộc một trong hai loại Ngược lại, nếu type bằng 3, thao tác sẽ xác định xem x và y có thuộc cùng một đội hay không, lưu ý rằng trong mọi trường hợp, x có thể bằng y.
Với các thao tác type= 3 in ra 'YES' hoặc 'NO' (không có dấu nháy) tùy theo hai người tương ứng có cùng một đội hay không?
Subtask 2 (20%): Chỉ có quyết định loại 1; n , q ≤ 2.10 5
Subtask 3 (20%): Chỉ có quyết định loại 2; n , q ≤ 2.10 5
Ta sử dụng cấu trúc dữ liệu "Disjoint Set" (trong thuật toán Kruskal) để giải quyết bài toán này.
Xây dựng đồ thị với các đỉnh là các nhân viên ( n đỉnh)
Mảng int a[ ] duy trì các thành phần liên thông của đồ thị
Mảng int b[ ] với ý nghĩa b[u]=v ( v ≥ u ¿ với ý nghĩa là các đỉnh u , u+1 , … , v đã được nhập với nhau thành một thành phần liên thông Khởi đầu a [ i ] =b [ i ] =i Lần lượt xét hai loại thao tác:
Với thao tác 1 x y: Đơn giản chỉ là nhập đỉnh x với đỉnh y vào cùng một thành phần liên thông void JoinA(x,y) { x=TimA(x), y=TimA(y); if (x!=y) a[x]=y;
Với thao tác 2 x y: while (1) { z=TimB(x)+1; // z là đỉnh đầu tiên >x mà chưa được nhập vào x nhờ thao tác 2 if (z>y) break; b[z-1]=z;
Nhắc lại hai hàm TimA và TimB: int TimA(u) { if (a[u]==u) return u; a[u]=TimA(a[u]); return a[u];
} int TimB(u) { if (b[u]==u) return u; b[u]=TimB(b[u]); return b[u];
Chương trình, test chấm: https://www.dropbox.com/sh/o5unxwd62o6zvh4/AAAiXpSZNl7wpHGoobi3 4Wara?dl=0
Bài 6 Kho báu (Nguồn: FreeContest)
Có N chiếc rương kho báu, chiếc rương thứ i có giá trị là C i Ban đầu, có
Mỗi chiếc chìa khóa thứ i có khả năng mở một trong hai chiếc rương A i hoặc B i, nhưng không thể mở cả hai rương cùng lúc Các rương chỉ được mở một lần duy nhất và việc sử dụng tất cả chìa khóa là không bắt buộc.
Trong bài toán này, cho một truy vấn K, truy vấn thứ nhất yêu cầu loại bỏ chiếc chìa khóa thứ P i mà không đánh số lại các chìa khóa còn lại Sau mỗi truy vấn, cần xác định tổng giá trị kho báu tối đa có thể thu được từ các rương được mở bằng cách sử dụng các chìa khóa còn lại theo cách tối ưu nhất.
Dòng đầu tiên gồm ba số nguyên N , K (2≤ N ≤ 200000 , 1 ≤ K ≤ 200000)
— số rương kho báu, số chìa khóa đồng thời là số truy vấn.
Dòng tiếp theo, gồm N số nguyên C 1 , C 2 , ,C N (1≤ C i ≤ 10 9 ) — giá trị của các rương kho báu.
K dòng tiếp theo, dòng thứ i gồm hai số nguyên
A i và B i (1 ≤ A i , B i ≤ N , A i ≠ B i ) — mô tả chiếc chìa khóa thứ i
Dòng tiếp theo, gồm K số nguyên phân biệt P 1 , P 2 , , P K (1 ≤ P i ≤ K )
— mô tả các truy vấn.
In ra K dòng, dòng thứ i gồm một số nguyên là tổng giá trị kho báu lớn nhất thu được sau khi thực hiện truy vấn thứ i
Sau khi thực hiện truy vấn đầu tiên, chúng ta còn lại các chìa khóa 1, 2 và 3 Chìa khóa 1 có thể mở rương 2, chìa khóa 2 mở rương 3 và chìa khóa 3 dùng để mở rương 1 Tổng giá trị của các rương được mở là 9 + 5 + 7.
Sau truy vấn thứ hai, chỉ còn lại chìa khóa 2 và 3 Chìa khóa 2 có thể mở rương 3, trong khi chìa khóa 3 mở rương 1 Tổng giá trị của các rương được mở là 9 + 7.
Sau truy vấn thứ ba, chỉ còn lại chìa khóa 3 Ta dùng chìa khóa này để mở rương 1 với giá trị 9.
Sau truy vấn thứ tu, ta không còn chiếc chìa khóa nào nên không mở được bất kì rương kho báu nào.
Subtask 3 (50% số điểm): Không có ràng buộc gì thêm.
Để giải bài toán mở rương tối ưu với K chìa khóa, ta cần xây dựng một đồ thị gồm N đỉnh, trong đó mỗi đỉnh i đại diện cho một chiếc rương Mỗi chìa khóa thứ i sẽ tạo ra một cạnh kết nối giữa đỉnh A i và B i Việc sử dụng chìa khóa i để mở rương A i hoặc B i tương đương với việc xác định hướng của cạnh i Do đó, chiếc rương thứ i sẽ được mở nếu có ít nhất một cạnh đi vào đỉnh i.
Khi đó, xét từng thành phần liên thông (TPLT):
Nếu TPLT tồn tại chu trình p1, p2, , pk, ta có thể định hướng các cạnh theo thứ tự p1 → p2 → p3 → → pk → p1 Sau đó, sử dụng thuật toán DFS từ các đỉnh trong chu trình, khi thăm đỉnh v từ đỉnh u, ta định hướng cạnh u → v Như vậy, mọi đỉnh trong TPLT sẽ có ít nhất một cạnh đi vào.
Nếu TPLT hiện tại không có chu trình, ta bắt đầu từ đỉnh đại diện cho kho báu có giá trị thấp nhất (đỉnh r) và áp dụng thuật toán DFS Trong quá trình này, tất cả các đỉnh trong TPLT ngoại trừ r sẽ có ít nhất một cạnh đi vào.
Do đó, đáp án sẽ là tổng giá trị các kho báu trừ đi tổng giá trị nhỏ nhất của các kho báu trong mỗi TPLT.
Quay trở lại với bài toán ban đầu, thao tác xóa chìa khóa tương ứng với việc xóa cạnh trong đồ thị Chúng ta sẽ thực hiện các truy vấn theo thứ tự ngược lại: bắt đầu với một đồ thị không có cạnh nào và mỗi truy vấn sẽ thêm một cạnh vào đồ thị.
Để giải quyết bài toán, ta có thể sử dụng cấu trúc dữ liệu disjoint-set union (DSU) Mỗi thành phần liên thông sẽ được lưu trữ thêm thông tin về đỉnh có giá trị nhỏ nhất.
Kho báu (TREASURE.CPP)
Độ phức tạp: O(N + K logK) hoặc O(N + Kα(K)) (với α(K) là nghịch đảo hàm Ackermann, có thể xem như hằng số), tùy vào cách cài đặt DSU.
Chương trình, test chấm: https://www.dropbox.com/sh/o5unxwd62o6zvh4/AAAiXpSZNl7wpHGoobi34Wara?dl=0
3.3 Dạng toán liên quan đến cây khung
Bài 7 Hệ thống điện (Nguồn: FreeContest) Đất nước Free Contest gồm N thành phố được đánh số từ 1 đến N Có M đường dây dẫn có thể xây dựng được, đường dây dẫn thứ i kết nối hai thành phố U i và V i với chi phí xây dựng là W i
Chính phủ Free Contest đang triển khai kế hoạch xây dựng lưới điện quốc gia nhằm cung cấp điện cho tất cả các thành phố Họ dự kiến sẽ lắp đặt hai trạm phát điện tại hai thành phố khác nhau và xây dựng nhiều đường dây dẫn để đảm bảo mọi thành phố đều có nguồn điện Một thành phố sẽ được cung cấp điện nếu có trạm phát điện đặt tại đó hoặc nếu nó có đường dây kết nối với một thành phố khác đã được cung cấp điện.
Chính phủ đã đề xuất hai phương án xây dựng hai trạm phát điện Phương án thứ nhất là đặt các trạm tại hai thành phố A i và B i Mỗi phương án yêu cầu tính toán tổng chi phí tối thiểu để xây dựng hệ thống đường dây điện, đảm bảo tất cả các thành phố đều được cung cấp điện.
Bạn là một lập trình viên xuất sắc tại Free Contest, được chính phủ tin tưởng giao cho nhiệm vụ quan trọng này Hãy hoàn thành nhiệm vụ một cách xuất sắc để thể hiện khả năng của mình!
Dòng đầu tiên gồm hai số nguyên N , M ( 1≤ N ≤ 4000 , 1 ≤ M ≤ 400000) - số thành phố của đất nước Free Contest và số đường dây dẫn có thể xây dựng.
M dòng tiếp theo, mỗi dòng gồm ba số nguyên U i , V i và
Mỗi đường dây dẫn thứ i được mô tả bởi W i (1 ≤ U i , V i ≤ N , U i ≠ V i , 1≤ W i ≤10 9 ) Dữ liệu đầu vào đảm bảo rằng nếu xây dựng toàn bộ M đường dây, thì từ bất kỳ thành phố nào cũng có thể truyền điện đến một thành phố khác thông qua các đường dây dẫn đã được thiết lập.
Dòng tiếp theo gồm một số nguyên Q (1 ≤Q ≤ 200000) - số phương án chính phủ đã đề xuất.
Q dòng tiếp theo, mỗi dòng gồm hai số nguyên
A i và B i (1 ≤ A i , B i ≤ N , A i ≠ B i ) mô tả phương án thứ i.
Đối với mỗi phương án, hãy tính toán và đưa ra một số nguyên duy nhất, đại diện cho tổng chi phí tối thiểu cần thiết để xây dựng các đường dây điện, đảm bảo rằng mọi thành phố đều được cung cấp điện đầy đủ.
Subtask 4 (25% số điểm): Không có ràng buộc gì thêm
Hình vẽ minh họa cho ví dụ đầu tiên với các đường dây dẫn được thể hiện bằng nét đứt cho những tuyến có thể xây dựng, trong khi các đường dây cần xây dựng được biểu diễn bằng nét liền Đỉnh màu đen trong hình đại diện cho thành phố nơi đặt trạm phát điện.
Để tối ưu hóa việc đặt trạm điện tại hai thành phố A và B, ta có thể xem như chỉ cần đặt trạm tại A và xây dựng đường dây điện nối với B với chi phí 0 Từ đó, chúng ta phát triển thuật toán cho hai subtask đầu tiên bằng cách bổ sung cạnh (A, B, 0) và tìm cây khung cực tiểu (minimum spanning tree) của đồ thị M với thuật toán Kruskal, có độ phức tạp O(QM log(N + M)) Để cải tiến thuật toán, cần hiểu rõ bản chất của Kruskal, bắt đầu bằng việc tìm cây khung cực tiểu T của đồ thị M cạnh Khi thêm cạnh trọng số 0 giữa A và B, cạnh này sẽ nằm trong cây khung tối thiểu, tạo thành chu trình với đường đi giữa A và B trong T, dẫn đến việc cạnh có trọng số lớn nhất trên đường đi sẽ bị loại bỏ khỏi cây khung cực tiểu.
Gọi W là tổng trọng số của các cạnh trong cây T, và maxW(u,v) là trọng số lớn nhất trên đường đi giữa hai đỉnh u và v trong T Đối với mỗi truy vấn i, đáp án được tính bằng W − maxW(Ai, Bi) Với độ phức tạp O(M log(N + M) + QN), chúng ta đã vượt qua subtask 3 Để đạt điểm tối đa, cần tính toán maxW(u,v) cho mọi cặp (u,v) trong O(N²) bằng cách sử dụng DFS từ từng đỉnh, cho phép mỗi truy vấn được trả lời trong O(1) Tổng độ phức tạp của thuật toán là O(M log(N + M) + N² + Q).
Chương trình, test chấm: https://www.dropbox.com/sh/o5unxwd62o6zvh4/AAAiXpSZNl7wpHGoobi34Wara?dl=0
Bài 8 Đơn giản hóa trang trại (Nguồn: FreeContest)
Nông dân John (FJ) đang theo học một lớp thuật toán buổi tối tại trường đại học gần nhà và vừa hoàn thành bài học về thuật toán tìm cây khung có tổng trọng số nhỏ nhất Nhờ đó, FJ nhận ra rằng thiết kế trang trại của mình chưa tối ưu và ông muốn đơn giản hóa bố trí của trang trại để nâng cao hiệu quả hoạt động.
Trang trại được mô phỏng như một đồ thị, trong đó các đỉnh đại diện cho các cánh đồng và các cạnh là các đường đi giữa chúng, với mỗi đường đi có độ dài xác định FJ nhận thấy rằng với mỗi độ dài khác nhau, có tối đa ba đường đi tương ứng Mục tiêu của FJ là loại bỏ một số đường đi để biến trang trại thành một cây, nghĩa là chỉ có một đường đi duy nhất giữa hai cánh đồng Hơn nữa, FJ mong muốn cây này trở thành cây khung với tổng trọng số nhỏ nhất.
FJ cần tính toán tổng độ dài các cạnh của cây khung nhỏ nhất từ đồ thị của trang trại của ông Đồng thời, ông cũng muốn biết số cách khác nhau để xây dựng cây khung này.
Dòng đầu tiên gồm hai số nguyên N , M( 1≤ N ≤ 4.10 4 , 1≤ M ≤ 10 5 ) biểu diễn số đỉnh và số cạnh của đồ thị Các đỉnh được đánh số từ 1 đến N
M dòng tiếp theo, dòng thứ i ghi ba số a i , b i và
L i (1 ≤a i , b i ≤ N , 1 ≤ L i ≤ 10 6 ) biểu thị có một cạnh nối a i với b i có chiều dài L i Không có quá ba cạnh có cùng chiều dài.
Có hai số nguyên cần được tính toán: số thứ nhất là tổng trọng số của cây khung nhỏ nhất, trong khi số thứ hai là số lượng cách khác nhau để tạo ra cây khung nhỏ nhất, với kết quả được lấy phần dư khi chia cho 10^9 + 7.
Để giải quyết bài toán, chúng ta cần đếm số lượng cây khung tối tiểu khác nhau Mỗi giá trị khoảng cách chỉ có tối đa ba cạnh có độ dài tương ứng Do đó, trong thuật toán Kruskal, chúng ta sẽ ghi nhận số lượng cạnh tham gia vào cây khung nhỏ nhất Các trường hợp có thể xảy ra sẽ được phân tích dựa trên thông tin này.
Giá trị của một cạnh trong cây khung chỉ được tham gia một lần Để tạo cây khung, cần thử nghiệm từng cạnh có giá trị này bằng cách sử dụng Disjoint Set một cách độc lập Số lần thao tác nhập được thực hiện sẽ tương ứng với kết quả cuối cùng, có thể là 1, 2 hoặc 3.
Đơn giản hóa trang trại (SIMPLIFY.cpp)
Tiệc khiêu vũ
Mehrad muốn tổ chức một buổi khiêu vũ tại cung điện và đã quyết định mời một số thiếu nữ tham gia Mỗi thiếu nữ được đặc trưng bởi cân nặng (w i) và vẻ đẹp (b i), đồng thời có thể thuộc về một nhóm bạn bè riêng Các thiếu nữ được phân chia thành từng nhóm dựa trên mối quan hệ bạn bè, trong đó thiếu nữ x và y được xem là cùng nhóm nếu tồn tại một chuỗi bạn bè liên kết họ.
Arpa cho phép Mehrad sử dụng giảng đường hoàng gia để tổ chức bữa tiệc Giảng đường này chỉ chịu được cân nặng tối đa là w
Merhad muốn mời những thiếu nữ có vẻ đẹp lớn nhất mà không làm tổn thương ai và đảm bảo trọng lượng của họ không vượt quá w Tuy nhiên, anh chỉ có thể mời cả nhóm bạn hoặc không mời quá một người Hãy giúp Merhad tìm ra những thiếu nữ xinh đẹp nhất mà anh có thể mời mà vẫn giữ được sự tôn trọng và không gây tổn thương cho những người khác.
Dòng đầu tiên nhập vào các số n , m , w - số thiếu nữ, số cặp tình bạn và cân nặng tối đa mà giảng đường chịu được.
Dòng thứ hai nhập vào n số w 1 , w 2 , … , w n (1≤ w i ≤ 1000) - cân nặng của mỗi thiếu nữ.
Dòng thứ ba nhập vào n số b 1 , b 2 , … , b n (1 ≤b i ≤ 10 6 ) - vẻ đẹp của mỗi thiếu nữ.
m dòng tiếp theo là các cặp tình bạn, dòng thứ i chứa cặp số nguyên x i và y i (1 ≤ x i , y i ≤ n , x i ≠ y i ), x i và y i là bạn Lưu ý rằng A là bạn B thì
B cũng là bạn A , các cặp bạn đôi một khác nhau.
Mehrdad cần mời các thiếu nữ với vẻ đẹp tối đa mà không làm tổn thương ai và đảm bảo tổng trọng lượng không vượt quá w.
PARTY.INP PARTY.OUT PARTY.INP PARTY.OUY
Trong ví dụ này, nhóm bạn {1, 2} có tổng cân nặng là 5 và tổng vẻ đẹp là 6 Để có sự lựa chọn tốt nhất, ta nên mời cả nhóm {1, 2} tham gia.
Trong ví dụ này, có hai nhóm bạn: nhóm {1, 2, 3} và nhóm riêng {4} Merhad không thể mời tất cả thành viên trong nhóm {1, 2, 3} vì tổng cân nặng của họ là 12, vượt quá giới hạn 11 Do đó, lựa chọn tối ưu là mời một người từ nhóm 1 và người từ nhóm 4, cụ thể là chọn người 1 và người 4.
4, cân nặng của họ bằng 8 và vẻ đẹp bằng 7.
Để bắt đầu, chúng ta cần phân chia các cô gái thành các nhóm bạn theo yêu cầu của đề bài Việc lập nhóm rất quan trọng vì mỗi nhóm có cách chọn lựa riêng biệt Nếu anh ta quyết định chọn cả nhóm, chúng ta cần biết thành viên của nhóm đó Ngược lại, nếu chỉ chọn một người đại diện, chúng ta cũng cần nắm rõ danh sách các cô gái trong nhóm.
Coi mỗi người bạn như một đỉnh trong đồ thị, ta có thể sử dụng cấu trúc dữ liệu DSU để nhóm các đỉnh có cùng gốc lại với nhau Khi hai người bạn kết nối, điều này tương đương với việc hai đỉnh này có một cạnh chung nối liền với nhau Độ phức tạp của thuật toán là O(m + log(n)).
Khi hoàn thành xong bước lập nhóm, ta nhận thấy rằng n có giới hạn khá bé (n ≤1000) nên ta sẽ đoán rằng thuật toán sẽ gồm 2 for
Cân nặng tối đa trong bài toán này được xác định là w≤1000, từ đó chúng ta có thể nhận thấy rằng đây là một bài toán quy hoạch động dựa trên trọng số.
Đề bài yêu cầu tìm vẻ đẹp tối đa mà không vượt quá trọng lượng w Ta định nghĩa dp[i] là giá trị vẻ đẹp lớn nhất mà các thiếu nữ có thể đạt được mà không vượt quá i Từ đó, chúng ta áp dụng quy hoạch động để tính toán dp[w], đây chính là kết quả cần in ra Công thức quy hoạch động sẽ được xác định dựa trên các yếu tố này.
+ j là chỉ số của các thiếu nữ trong nhóm.
H - Height Preservation
Thực tế ảo (VR) đang trở thành xu hướng nổi bật, mang đến trải nghiệm độc đáo trong các lĩnh vực giáo dục và giải trí Để nâng cao trải nghiệm người dùng, ICPC đã thiết lập phòng VR, cho phép người dùng khám phá môi trường ảo Tại đây, người dùng không chỉ nhìn thấy cảnh vật ảo qua thiết bị VR mà còn cảm nhận được độ dốc của địa hình khi di chuyển trong không gian ảo đó.
Phòng VR được cấu tạo bởi m × n ô, trong đó m là số hàng và n là số cột Chiều cao thực của mỗi ô có thể được điều chỉnh để mô phỏng địa hình ảo Mỗi ô (i, j) có độ cao thực S(i, j) tương ứng với độ cao ảo H(i, j) trong cảnh ảo Mục tiêu chính của việc mô phỏng địa hình ảo là bảo toàn thứ tự tương đối của chiều cao các ô trong từng hàng và cột.
- Trong mỗi hàng i(1≤ i≤ m ), S(i , j)=S (i ,k ) nếu H (i , j)= H (i, k ) và
- Trong mỗi cột j(1 ≤ j ≤n) , S (i, j)= S (k , j ) nếu H (i , j)=H (k , j ) và
Yêu cầu: Cho chiều cao ảo của tất cả các ô, nhiệm vụ của bạn là xác định số lượng ít nhất các mức chiều cao thực khác nhau.
Dòng đầu tiên chứa hai số nguyên dương: m và n , tương ứng với số lượng hàng và cột (m ×n ≤ 10 6 ).
Dòng thứ i trong m hàng chứa n số nguyên dương H (i , j) ≤10 9 tương ứng với chiều cao ảo của các ô trong hàng thứ i
Đưa ra số nguyên là số số lượng ít nhất các mức chiều cao thực khác nhau trong phòng VR.
Để gộp các ô có giá trị giống nhau, trước tiên chúng ta sẽ xác định các ô thuộc cùng một dòng hoặc cột và nhóm chúng thành một thành phần liên thông, gọi là siêu đỉnh Quá trình tìm kiếm các cặp ô để gộp có thể thực hiện bằng cách duyệt từng dòng, sắp xếp các ô theo thứ tự tăng dần, và thêm cạnh giữa hai ô nằm ở cột j và cột j+1 nếu giá trị của chúng bằng nhau Tương tự, chúng ta cũng áp dụng quy trình này cho từng cột Việc gộp ô có thể được thực hiện thông qua các phương pháp như DSU hoặc DFS.
Sau khi duyệt từng dòng, chúng ta sắp xếp các ô theo thứ tự tăng dần Tiếp theo, chúng ta thêm cạnh một chiều từ siêu đỉnh chứa ô ở cột j đến siêu đỉnh chứa ô ở cột j+1 của dòng hiện tại, nếu số ở cột j nhỏ hơn số ở cột j+1 Quy trình này được thực hiện tương tự cho từng cột.
Cuối cùng, chúng ta sẽ có một đồ thị có hướng không chu trình (DAG) trên các siêu đỉnh Đáp số cần tìm là số đỉnh trên đường đi dài nhất của DAG này Bài toán tìm độ dài đường đi dài nhất trên DAG là một bài toán quy hoạch động cổ điển, có thể được giải trong thời gian O(N+M), trong đó N là số đỉnh và M là số cạnh của DAG Độ phức tạp của bài toán này là O(N*M*log(N+M)).
Chấm bài tại: https://hochiminh17.kattis.com/problems/heightpreservation
