Hãy xem xét một quốc gia được biểu diễn dưới dạng cây có N nút và N-1 cạnh. Bây giờ mỗi nút đại diện cho một thị trấn và mỗi cạnh đại diện cho một con đường. Chúng tôi có hai danh sách số nguồn và số cuối có kích thước N-1. Theo họ con đường thứ i nối nguồn [i] đến đích [i]. Và những con đường là hai chiều. Chúng tôi cũng có một danh sách các số khác được gọi là dân số cỡ N, trong đó dân số [i] đại diện cho dân số của thị trấn thứ i. Chúng tôi đang cố gắng nâng cấp một số thị trấn thành thành phố. Nhưng không có hai thành phố nào liền kề với nhau và mọi nút tiếp giáp với một thị trấn phải là một thành phố (mọi con đường phải nối một thị trấn và một thành phố). Vì vậy, chúng tôi phải tìm ra dân số tối đa có thể có của tất cả các thành phố.
Vì vậy, nếu đầu vào giống như nguồn =[2, 2, 1, 1] dest =[1, 3, 4, 0] dân số =[6, 8, 4, 3, 5], thì đầu ra sẽ là 15, vì chúng ta có thể nâng cấp các thành phố 0, 2 và 4 để có dân số 6 + 4 + 5 =15.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- adj:=tạo danh sách biểu đồ liền kề bằng cách sử dụng nguồn và đích
- Định nghĩa một hàm dfs (). Điều này sẽ lấy x, chọn
- nếu x được nhìn thấy, thì
- trả về 0
- đánh dấu x là đã thấy
- ans:=0
- nếu lựa chọn là đúng, thì
- ans:=ans + dân số [x]
- đối với mỗi hàng xóm trong adj [x], thực hiện
- ans:=ans + dfs (hàng xóm, nghịch đảo của lựa chọn)
- trả lại ans
- Từ phương thức chính, hãy làm như sau:
- x:=dfs (0, True)
- trả về tối đa x và ((tổng dân số) - x)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
from collections import defaultdict class Solution: def solve(self, source, dest, population): adj = defaultdict(list) for a, b in zip(source, dest): adj[a].append(b) adj[b].append(a) seen = set() def dfs(x, choose): if x in seen: return 0 seen.add(x) ans = 0 if choose: ans += population[x] for neighbor in adj[x]: ans += dfs(neighbor, not choose) return ans x = dfs(0, True) return max(x, sum(population) - x) ob = Solution() source = [2, 2, 1, 1] dest = [1, 3, 4, 0] population = [6, 8, 4, 3, 5] print(ob.solve(source, dest, population))
Đầu vào
[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]
Đầu ra
15