เวลาขั้นต่ำในการรวบรวมแอปเปิ้ลทั้งหมดในต้นไม้ใน C++

สมมติว่าเรามีต้นไม้ที่ไม่มีทิศทางที่ประกอบด้วยจุดยอด n จุด และมีตัวเลขตั้งแต่ 0 ถึง n-1 ซึ่งมีแอปเปิลบางส่วนอยู่ในจุดยอด เราใช้เวลา 1 วินาทีในการเดินบนขอบไม้ด้านหนึ่ง เราต้องหาเวลาขั้นต่ำเป็นวินาทีที่เราต้องใช้เพื่อเก็บแอปเปิลทั้งหมดในต้นไม้โดยเริ่มจากจุดยอด 0 และกลับมาที่จุดยอดนี้

ในที่นี้ ขอบของต้นไม้ที่ไม่มีทิศทางจะได้รับในขอบอาร์เรย์ โดยที่ edge[i] =[from_i, to_i] หมายความว่ามีขอบที่เชื่อมระหว่างจุดยอด from_i และ to_i นอกจากนี้ยังมีอาร์เรย์อื่นที่มี apple โดยที่ hasApple[i] =true หมายความว่าจุดยอด i มีแอปเปิล มิฉะนั้น จะไม่มีแอปเปิล

ดังนั้น ถ้าอินพุตเป็น n =7 และ edge =[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]] และมี apple =[false, false, true, false, true, true, false] ดังนั้นผลลัพธ์จะเป็น 8

จากภาพด้านบนจะเห็นต้นไม้ที่มีจุดยอดสีแดงมีแอปเปิ้ล ลูกศรสีเขียวแสดงเส้นทางที่เหมาะสมที่สุดในการรวบรวมแอปเปิ้ลทั้งหมด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดการเยี่ยมชมหนึ่งชุด

• กำหนดฟังก์ชัน dfs() ซึ่งจะรับ node, par, array a, an array graph[],

• อุณหภูมิ :=0

• สำหรับแต่ละองค์ประกอบ x ในกราฟ[โหนด] −

  • ถ้า x เท่ากับพาร์ แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • temp :=temp + dfs(x, node, a, กราฟ)

• ret :=ret + temp * 2

• คืนค่า true เมื่อ a[node] + temp> 0 มิฉะนั้น 0

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ยกเลิก :=0

• กำหนดอาร์เรย์ของ n รายการที่เรียกว่ากราฟ

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ e อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • แทรก e[i, 1] ที่ส่วนท้ายของกราฟ[e[i, 0]]

  • แทรก e[i, 0] ที่ส่วนท้ายของกราฟ[e[i, 1]]

• dfs(0, -1, a, กราฟ)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;const int N =1e6;โซลูชันคลาส {สาธารณะ:ชุด  เข้าชมแล้ว; int ret; int dfs (โหนด int, int par, vector&a, vector กราฟ[]){ int temp =0; สำหรับ (int x:กราฟ [โหนด]) { ถ้า (x ==พาร์) ดำเนินการต่อ; อุณหภูมิ +=dfs(x, โหนด, a, กราฟ); } ret +=อุณหภูมิ * 2; ส่งคืน [โหนด] + อุณหภูมิ> 0; } int minTime(int n, vector>&e, vector&a){ ret =0; เวกเตอร์ กราฟ[n]; สำหรับ (int i =0; i > v ={{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}}; vector v1 ={เท็จ,เท็จ,จริง,เท็จ,จริง,จริง,เท็จ}; cout <<(ob.minTime(7,v, v1));}

อินพุต

ผลลัพธ์

8