พิจารณาประเทศที่แสดงเป็นต้นไม้ที่มีโหนด N และขอบ N-1 ตอนนี้แต่ละโหนดแสดงถึงเมือง และแต่ละขอบแสดงถึงถนน เรามีรายการตัวเลขแหล่งที่มาและปลายทางของขนาด N-1 สองรายการ ตามที่พวกเขากล่าว ถนนที่ i เชื่อมระหว่างแหล่ง[i] กับ dest[i] และถนนเป็นแบบสองทิศทาง นอกจากนี้เรายังมีรายการตัวเลขอีกรายการหนึ่งที่เรียกว่า ประชากรขนาด N โดยที่ประชากร[i] หมายถึงประชากรของเมืองที่ i เรากำลังพยายามอัพเกรดเมืองบางเมืองให้เป็นเมืองต่างๆ แต่ไม่ควรมีเมืองสองเมืองติดกัน และทุกโหนดที่อยู่ติดกับเมืองควรเป็นเมือง (ถนนทุกสายต้องเชื่อมระหว่างเมืองกับเมือง) ดังนั้นเราจึงต้องหาจำนวนประชากรสูงสุดที่เป็นไปได้ของเมืองทั้งหมด
ดังนั้น หากอินพุตเป็นเหมือนแหล่ง =[2, 2, 1, 1] ปลายทาง =[1, 3, 4, 0] ประชากร =[6, 8, 4, 3, 5] ผลลัพธ์จะเป็น 15 เนื่องจากเราสามารถอัปเกรดเมือง 0, 2 และ 4 เพื่อให้ได้ประชากร 6 + 4 + 5 =15
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- adj :=สร้างรายการที่อยู่ติดกันของกราฟโดยใช้แหล่งที่มาและปลายทาง
- กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา x เลือก
- ถ้าเห็น x แล้ว
- คืน 0
- ทำเครื่องหมาย x ตามที่เห็น
- ตอบ :=0
- ถ้าเลือกเป็นจริง
- ans :=ans + ประชากร[x]
- สำหรับเพื่อนบ้านแต่ละคนใน adj[x], do
- ans :=ans + dfs(เพื่อนบ้าน, ผกผันของการเลือก)
- คืนสินค้า
- จากวิธีหลัก ให้ทำดังนี้:
- x :=dfs(0, True)
- ผลตอบแทนสูงสุดของ x และ ((ผลรวมของประชากร) - x)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]
ผลลัพธ์
15
