Giả sử, chúng ta có một cây với n đỉnh, trong đó mỗi đỉnh được đánh nhãn từ 1 đến n. Gốc của cây có nhãn 1, và mỗi đỉnh có trọng số bằng wi. Bây giờ một ma trận nxn A được tạo thành trong đó A (x, y) =Wf (x, y) trong đó f (x, y) là bậc tiền bối nhỏ nhất của đỉnh x và y. Chúng ta phải tìm ra định thức của ma trận A. Các cạnh của ma trận, trọng số và tổng số đỉnh được cung cấp cho chúng ta làm đầu vào.
Vì vậy, nếu đầu vào giống như input_array =[[1, 2], [1, 3], [1, 4], [1, 5]], weights =[1, 2, 3, 4, 5], vertices =5, thì đầu ra sẽ là 24.
Ma trận A được cho là =
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 1 | 1 | 1 |
| 1 | 1 | 3 | 1 | 1 |
| 1 | 1 | 1 | 4 | 1 |
| 1 | 1 | 1 | 1 | 5 |
định thức của ma trận này là 24.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- w:=một danh sách trống
- đối với tôi trong phạm vi 0 đến đỉnh, thực hiện
- thêm trọng số [i] và một danh sách mới vào w
- đối với mỗi i, mục trong liệt kê (input_array), thực hiện
- p:=item [0]
- q:=item [1]
- chèn q - 1 vào cuối w [p - 1, 1]
- chèn p - 1 vào cuối w [q - 1, 1]
- det:=1
- ngăn xếp:=ngăn xếp chứa một bộ giá trị (0, 0)
- trong khi ngăn xếp không trống, hãy thực hiện
- i, weights:=xóa phần tử trên cùng khỏi ngăn xếp
- det:=(det * (w [i, 0] - weights)) mod (10 ^ 9 + 7)
- for t in w [i] [1], do
- thêm bộ chứa (t, w [i, 0]) vào ngăn xếp
- đối với mỗi t trong w [i] [1], thực hiện
- xóa tôi khỏi w [t, 1]
- trả về det
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(input_array, weights, vertices): w = [[weights[i],[]] for i in range(vertices)] for i, item in enumerate(input_array): p,q = item[0], item[1] w[p - 1][1].append(q - 1) w[q - 1][1].append(p - 1) det = 1 stack = [(0,0)] while stack: i, weights = stack.pop() det = (det * (w[i][0] - weights)) % (10**9 + 7) stack += [(t,w[i][0]) for t in w[i][1]] for t in w[i][1]: w[t][1].remove(i) return det print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))
Đầu vào
[[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5
Đầu ra
24