Giả sử có một đồ thị có trọng số với n đỉnh và m cạnh. Các cạnh có trọng số là lũy thừa của 2. Bất kỳ đỉnh nào cũng có thể đến được từ đỉnh khác, và chi phí đi lại là tổng trọng số các cạnh trên đường đi. Ta phải xác định tổng chi phí tối thiểu giữa mỗi cặp đỉnh.
Ví dụ, với đầu vào như hình minh họa và số đỉnh n = 6, đầu ra sẽ là 2696.
Tổng tất cả các khoảng cách là 2696.
Giải pháp
Để giải quyết bài toán này, ta thực hiện các bước sau:
- Định nghĩa hàm par_finder(i, par):
- Nếu par[i] == -1, trả về i
- res := par_finder(par[i], par)
- par[i] := res
- Trả về res
- Định nghĩa hàm helper(i, par, w, G, n):
- child := 1
- Với mỗi item trong G[i]:
- Nếu item[0] == par, tiếp tục
- Ngược lại, child := child + helper(item[0], i, item[1], G, n)
- Nếu par != -1:
- ans := ans + child * (n - child) * (1 << w)
- Trả về child
- G := danh sách mới chứa n + 1 danh sách khác
- edges := danh sách mới
- Với mỗi item trong roads:
- u := item[0], v := item[1], w := item[2]
- Thêm (u-1, v-1, w) vào cuối edges
- Sắp xếp edges theo trọng số cạnh
- par := danh sách kích thước n + 1 khởi tạo bằng -1
- r_edge := danh sách mới
- Với mỗi i trong edges:
- Nếu par_finder(i[0], par) == par_finder(i[1], par), tiếp tục
- Ngược lại:
- Thêm i vào cuối r_edge
- Thêm cặp (i[1],i[2]) vào G[i[0]]
- Thêm cặp (i[0],i[2]) vào G[i[1]]
- par[par_finder(i[0], par)] := par_finder(i[1], par)
- ans := 0
- Gọi helper(0, -1, 0, G, n)
- Trả về ans
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def par_finder(i, par):
if par[i] == -1:
return i
res = par_finder(par[i], par)
par[i] = res
return res
def helper(i, par, w, G, n):
global ans
child = 1
for item in G[i]:
if item[0] == par:
continue
else:
child += helper(item[0], i, item[1], G, n)
if par != -1:
ans += child * (n - child) * (1 << w)
return child
def solve(n, roads):
global ans
G = [[] for i in range(n + 1)]
edges = []
for item in roads:
u, v, w = map(int, item)
edges.append((u-1, v-1, w))
edges = sorted(edges, key=lambda item: item[2])
par = [-1 for i in range(n + 1)]
r_edge = []
for i in edges:
if par_finder(i[0], par) == par_finder(i[1], par):
continue
else:
r_edge.append(i)
G[i[0]].append((i[1], i[2]))
G[i[1]].append((i[0], i[2]))
par[par_finder(i[0], par)] = par_finder(i[1], par)
ans = 0
helper(0, -1, 0, G, n)
return ans
print(solve(6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]))
Đầu vào
6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]
Đầu ra
2696