n lần Floyd
Thuật toán Floyd tiêu chuẩn có thứ tự duyệt như sau:
for (k) for (i) for (j)
kq[i][j] = min(kq[i][k] + kq[k][j])
Floyd tiêu chuẩn cho ta đường đi ngắn nhất không giới hạn số cạnh.
Nhưng nếu viết thành:
for (i) for (j) for (k)
ketqua[i][j] = min(kq[i][k] + a[k][j])
(trong đó \(ketqua\) là ma trận khởi tạo toàn giá trị vô cùng, \(kq,a\) ban đầu là ma trận kề, không có cạnh thì là vô cùng) thì đường đi ngắn nhất sẽ là đường đi qua đúng một đỉnh trung gian.
Nếu thực hiện n lần Floyd (sau mỗi lần cập nhật ma trận kq, lúc này ma trận \(kq\) biểu diễn đường đi qua n-1 đỉnh trung gian), ta được đường đi ngắn nhất qua đúng n đỉnh (đi qua n+1 cạnh).
Có thể tăng tốc bằng ma trận (nhân ma trận res[i][j] += a[i][k] * b[k][j] đổi thành res[i][j] = min(res[i][j], a[i][k] + b[k][j])).
Tất nhiên, nếu tính toán đúng theo quy tắc nhân ma trận, phần tử hàng u cột v của ma trận mũ k chính là số cách đi từ u đến v qua đúng k cạnh. Ví dụ: CF402E Strictly Positive Matrix
Đường kính của cây
Tính chất:
- Đường đi dài nhất trong cây.
- Không nhất thiết duy nhất.
- Trong cây, đỉnh xa nhất từ một đỉnh bất kỳ u chắc chắn là một trong hai đầu mút của đường kính.
- Các tính chất trên chỉ áp dụng khi trọng số các cạnh không âm.
Cách tính:
Cách 1: Hai lần BFS/DFS
Chọn một đỉnh bất kỳ, BFS tìm đỉnh xa nhất từ đỉnh đó là u; rồi từ u, BFS tìm đỉnh xa nhất từ u là v. Đường u -> v chính là một trong các đường kính của cây.
Phương pháp này áp dụng cho trường hợp trọng số cạnh không âm.
Cách 2: Quy hoạch động trên cây
Xem xét tìm đường kính tại LCA của nó. Với mỗi đỉnh lưu trữ f(x) là đường đi dài nhất đi xuống dưới từ đỉnh x. Với mỗi đỉnh, tìm tổng của hai giá trị lớn nhất và lớn thứ hai.
Mở rộng: "Đường kính ba nhánh"
Trong cây có trọng số cạnh bằng 1 (các trường hợp khác chưa nghiên cứu), ba đỉnh (x,y,z) tạo thành cây ảo có kích thước lớn nhất gọi là đường kính ba nhánh của cây đó.
Một số tính chất:
- Trong đường kính ba nhánh, hai trong ba đỉnh là hai đầu mút của đường kính.
- Khi thêm một đỉnh p, ba đỉnh (x,y,z) của đường kính ba nhánh sẽ thay đổi tối đa một đỉnh.
Trọng tâm của cây
Tính chất:
- Trọng tâm của cây là đỉnh mà khi lấy làm gốc, cây con lớn nhất có kích thước nhỏ nhất.
- Trọng tâm của cây là đỉnh mà tổng khoảng cách từ mọi đỉnh trong cây đến đỉnh đó là nhỏ nhất.
- Kích thước của mọi cây con của trọng tâm không vượt quá một nửa kích thước của cả cây. Đảo lại cũng đúng.
- Trọng tâm của cây không quá hai đỉnh. Nếu số đỉnh là lẻ thì có một trọng tâm; nếu chẵn thì có thể có hai. Nếu có hai, tồn tại một cạnh mà hai phía của nó đều có kích thước n/2.
- Khi thêm một đỉnh, trọng tâm di chuyển tối đa một vị trí.
- Khi nối hai cây, trọng tâm của cây mới nằm trên đường thẳng nối hai trọng tâm ban đầu.
- Với cây có gốc là rt, trọng tâm chắc chắn là rt, hoặc con nặng của rt, hoặc con nặng của con nặng của rt...
Cách tìm:
Quy hoạch động trên cây, lưu trữ kích thước cây con lớn nhất. Chọn đỉnh có cây con lớn nhất nhỏ nhất làm gốc.
Xem thêm: Phân chia đỉnh (point division)
Duy trì động trọng tâm 1
Hỗ trợ thêm cạnh, tìm trọng tâm.
Xem: P4299 首都
Dùng LCT để thêm cạnh động; DSU để duy trì rừng;
Áp dụng hai tính chất cuối, sau khi thêm cạnh lấy ra chuỗi nối hai trọng tâm, rồi tìm kiếm nhị phân trên cây Splay.
Duy trì nhanh trọng tâm 2
Tìm trọng tâm của mọi cây con có gốc là rt (n > Cách 1: Khi nối hai cây, trọng tâm của cây mới nằm trên đường thẳng nối hai trọng tâm ban đầu.
Có thể dùng phương pháp "Duy trì động trọng tâm 1", DFS thêm cạnh động; nhưng có cách brute force hơn là nhảy trực tiếp trên chuỗi để truy vấn. Có thể cảm nhận được độ phức tạp không cao (nhờ tính chất đẹp của trọng tâm) (không đến O(n^2)). Dùng LCT đạt O(nlogn)
Cách 2: Với cây có gốc là rt, trọng tâm chắc chắn là rt, hoặc con nặng của rt, hoặc con nặng của con nặng của rt...
Có thể sử dụng tính chất này để biết vị trí của trọng tâm nằm trên một chuỗi. Hơn nữa, ta thấy trọng tâm thỏa mãn n - siz Truy vấn: Trọng tâm của hai cây sau khi xóa mỗi cạnh.
Xem: P5666 树的重心
Thực ra bài này đặt ở D2T2 hoặc D1T3 có lẽ sẽ có nhiều người làm được hơn.
Do các thao tác không liên quan đến nhau, cần thêm cạnh động, xóa cạnh, tìm trọng tâm, nên không thể dùng thuật toán LCT ở trên (lúc đó tôi còn không biết Splay)
Dễ lấy 55 điểm, cần suy nghĩ cách lấy 45 điểm còn lại (n Trọng tâm của cây là đỉnh mà tổng khoảng cách từ mọi đỉnh trong cây đến đỉnh đó là nhỏ nhất.
Biết rằng công thức đạt giá trị nhỏ nhất khi và chỉ khi p là trọng tâm của cây. Có trọng số cũng không sao, coi như một chuỗi nội bộ có trọng số cạnh bằng 0.
Vậy cần duy trì nhanh trọng tâm của cây. Đặt F(x) = \(\sum_{u}val[u] * dis(u,x)\), bài CSP2019D2T3 cho thấy có thể dùng nhân đôi để tiền xử lý chuỗi "con nặng" để tìm nhanh trọng tâm, và có thể DP đổi gốc O(n) tính tất cả F(x), nhưng nếu cần hỗ trợ sửa đổi trọng số đỉnh, cạnh nặng nhẹ có thể thay đổi, sửa đổi brute force "chuỗi con nặng" và mảng nhân đôi dễ bị O(qnlogn), và tất cả F(x) đều thay đổi, phương pháp này sẽ thành brute force còn tệ hơn. Phải nghĩ cách khác.
Tuy nhiên, may mắn là tư tưởng "xác định vị trí gần đúng của trọng tâm dựa trên con nặng" vẫn áp dụng được trong bài này. Nếu chọn đại một đỉnh và biết con nặng của nó là ai, có thể tìm đáp án trong cây con của con nặng. Đây nhìn giống một bài toán con. Nếu đảm bảo số lần "đi vào cây con" không nhiều, có thể giải quyết được. Vì vậy dùng phân chia đỉnh để duy trì trọng tâm.
Còn hai vấn đề: tính nhanh F(x), và tìm nhanh con nặng.
Cảm nhận (chứng minh cũng không khó), F(con nặng) đỉnh duyệt trước)**
Ứng dụng: tarjan
Đường Euler & Chu trình Euler
Đường đi qua tất cả các cạnh gọi là đường Euler, nếu điểm đầu và cuối trùng nhau thì gọi là chu trình Euler.
Điều kiện:
- Đường Euler có hướng: Trong đồ thị liên thông yếu, mỗi đỉnh có 入度 = 出度, hoặc có một đỉnh 入度 = 出度 - 1, một đỉnh 入度 = 出度 + 1.
- Chu trình Euler có hướng: Trong đồ thị liên thông yếu, mỗi đỉnh có 入度 = 出度
- Đường Euler vô hướng: Liên thông, và có tối đa hai đỉnh có bậc lẻ.
- Chu trình Euler vô hướng: Liên thông, và mọi đỉnh đều có bậc chẵn.
Tìm lộ trình
Bắt đầu từ đỉnh xuất phát, DFS, mỗi lần tìm một cạnh chưa duyệt để đi. Sau khi DFS kết thúc, đưa đỉnh hiện tại vào stack. Cuối cùng, dãy trong stack (dãy ngược) chính là một đáp án.
Độ phức tạp: O(nm), dùng tối ưu cung có thể tối ưu thành O(n+m), nhưng cần dùng &i thay vì hcur[cur], nếu không vẫn là O(nm).
Code (ví dụ chu trình Euler vô hướng):
int stk[N], stop;
bool evis[NN];
void dfs(int cur) {
for (int &i = head[cur]; i; i = e[i].nxt) {
if (evis[i]) continue;
evis[i] = evis[i ^ 1] = true;
dfs(e[i].to);
}
stk[++stop] = cur;
}
Ứng dụng
Chạy chu trình Euler trên đồ thị vô hướng có thể định hướng các cạnh vô hướng, và sau khi định hướng mỗi đỉnh có 入度 = 出度. Nhờ đặc điểm này có thể làm một số bài xây dựng kiểu ghép đôi (như Mike and Fish và Two Trees)
Đồ thị thi đấu & Đường đi Hamilton
- Đồ thị thi đấu chắc chắn có đường đi Hamilton
- Đồ thị thi đấu liên thông mạnh chắc chắn có chu trình Hamilton (liên thông mạnh có chu trình Hamilton)
- Đồ thị thi đấu sau khi tarjan thu nhỏ thành DAG có thể kéo thành một chuỗi, trong đó các đỉnh phía sau đều có cạnh đến các đỉnh phía trước
Đồ thị thi đấu và chu trình Hamilton
Bài: Turysta
Cách xây dựng đường đi Hamilton: Phương pháp tăng dần
Cách xây dựng chu trình Hamilton: Trước xây dựng đường đi Hamilton, rồi dùng phương pháp tăng dần để xây dựng
//P3561
//Xây dựng chu trình Hamilton cho một thành phần liên thông mạnh
inline void make_chain(int c) {
for (int i = 1; i <= n; ++i) if (col[i] == c) {
l = r = i; break;
}
for (int i = l + 1; i <= n; ++i) if (col[i] == c) {
if (e[i][l]) nxt[i] = l, l = i;
else if (e[r][i]) nxt[r] = i, r = i;
else {
int p = l;
while (1) {
if (e[p][i] && e[i][nxt[p]]) {
nxt[i] = nxt[p];
nxt[p] = i;
break;
}
p = nxt[p];
}
}
}
}
inline void make_circle(int c) {
r = 0;
for (int i = nxt[l]; i; i = nxt[i]) {
if (r) {
for (int k = r, j = l; ; k = j, j = nxt[j]) {
if (e[i][j]) {
nxt[k] = nxt[r];
if (k != r) nxt[r] = l;
r = i; l = j;
break;
}
if (j == r) break;
}
} else if (e[i][l]) r = i;
}
if (r) nxt[r] = l;
else nxt[l] = l;
}
Đếm tam giác & Đếm tứ giác
Cho đồ thị vô hướng n đỉnh m cạnh, hỏi có bao nhiêu tam giác (chu trình đơn chỉ chứa ba đỉnh), bao nhiêu tứ giác. n,m ≤ 100000
Công cụ ít dùng - "Tam giác"
Định hướng đồ thị có hướng dựa trên bậc của các đỉnh, để đỉnh có bậc nhỏ hướng đến đỉnh có bậc lớn, khi bậc bằng nhau thì theo số thứ tự đỉnh để hướng. Sau khi xử lý như vậy, có thể đảm bảo mỗi đỉnh có không quá √m cạnh ra.
Rồi thấy tam giác (A,B,C) sẽ không tạo thành vòng tròn, chỉ có thể là A → B, A → C, B → C như vậy. Vậy ta thống kê đóng góp tại đỉnh được hai đỉnh cùng trỏ đến.
Độ phức tạp: O(m√m)
Bài: 旧试题
for (A) {
for (B)
mark B;
for (B)
for (C)
if (C is marked)
get a circle;
}
Tứ giác (A,B,C,D) có ba dạng định hướng:
A -> B -> C -> D | A -> D
A -> B -> C | A -> D -> C
A -> C | B -> C | A -> D | B -> D
Duyệt cạnh vô hướng ở lớp ngoài, cạnh có hướng ở lớp trong, thì cả ba trường hợp đều được thống kê.
Trong đó hai trường hợp đầu được tính một lần, trường hợp thứ ba được tính hai lần. Vì vậy cần ghi nhận hướng của cạnh từ đỉnh bắt đầu đến đỉnh giữa tại vị trí đếm, nếu thấy đều ngược thì cần xử lý đặc biệt.
Độ phức tạp: O(m√m)
for (A)
for (B)
for (C) {
get ans(dir, C);
mark(dir, C);
}
Tìm chu trình
Nếu là cây với chu trình (cây cơ sở có chu trình), cách thuận tiện nhất là sắp xếp topo. Các đỉnh chưa được đưa vào hàng đợi là các đỉnh trên chu trình.
Còn một cách là tarjan tìm e-DCC, xong không đi qua cạnh cầu rồi DFS lại. Cách này mạnh, có thể giải quyết nhiều chu trình và chu trình lồng nhau, nhưng tương đối khó viết.
Còn một cách thường dùng là DFS + stack. Duy trì stack của DFS hiện tại, gặp chu trình thì pop khỏi stack. Nhược điểm là không giải quyết tốt nhiều chu trình và chu trình lồng nhau, và rất dễ sai sau khi DFS với việc undo stack
Còn một cách là cây DFS. Sau khi tìm cây DFS, hình dạng chu trình chỉ có thể là một cạnh ngược lại (back edge) cộng với một chuỗi cây. Cách này có thể đơn giản hóa mô hình đồ thị, thuận tiện làm bài, cũng không khó viết. Cũng có thể giải quyết vấn đề chu trình lồng nhau (kết quả là tách thành nhiều chu trình đơn)