โปรแกรม C ++ เพื่อค้นหาผลรวมสูงสุดของกราฟที่เชื่อมต่อน้อยที่สุด

สมมติว่าเราได้รับกราฟที่เชื่อมต่อน้อยที่สุด นั่นหมายความว่าการลบขอบใด ๆ จะทำให้กราฟถูกตัดการเชื่อมต่อ กราฟมีจุดยอด n จุด และขอบอยู่ในอาร์เรย์ 'ขอบ' นอกจากนี้ยังมีอาร์เรย์ 'vertexValues' ที่มอบให้เราซึ่งมีค่าจำนวนเต็ม n ค่า

ตอนนี้ เราทำสิ่งต่อไปนี้ -

• เราเขียนจำนวนเต็มบวกบนจุดยอดแต่ละจุดแล้วลองคำนวณคะแนน

• มีขอบเชื่อมจุดยอดสองจุด เราใส่ค่าที่น้อยกว่าของจุดยอดทั้งสองที่ขอบ

• เราคำนวณคะแนนโดยเพิ่มค่าขอบทั้งหมด

เราต้องหาค่าสูงสุดที่สามารถทำได้โดยใส่ค่าลงบนจุดยอด เราต้องพิมพ์ค่ารวมสูงสุดและค่าที่จะเขียนบนจุดยอด

ดังนั้น หากอินพุตเป็น n =6, edge ={{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, vertexValues ​​={1, 2, 3, 4, 5, 6} แล้วผลลัพธ์จะเป็น 15, 3 1 2 4 5 6 เพราะเราสามารถใส่ค่าบนจุดยอดตั้งแต่ 0 ถึง n – 1 ในแบบที่กำหนด 3 1 2 4 5 6 .

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

N :=100 กำหนดอาร์เรย์ seq และ res ของขนาด N.กำหนดอาร์เรย์ tp ของขนาด N.ans :=0 กำหนดฟังก์ชัน dfs() ซึ่งจะใช้เวลา p, q, res[p] :=seq[c] ถ้า p ไม่เท่ากับ 0 ดังนั้น:ans :=ans + seq[c] (ลด c โดย 1) สำหรับแต่ละค่า x ใน tp[p] ให้ทำ:ถ้า x ไม่เท่ากับ q ดังนั้น:dfs(x , p) สำหรับการเริ่มต้น i :=0 เมื่อ i + 1 =0, update (ลด i โดย 1), do:print(res[ ผม])

ตัวอย่าง

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

#include using เนมสเปซ std;const int INF =1e9;#define N 100int seq[N], res[N];vector tp[N];int ans =0, c;void dfs(int p, int q) { res[p] =seq[c]; if(p !=0) ans +=seq[c]; ค--; สำหรับ (อัตโนมัติ x :tp [p]) { ถ้า (x !=q) dfs (x, p); }} โมฆะ แก้(int n, vector> edge, int vertexValues[]){ for(int i =0; i + 1 =0; i--) cout <> ขอบ ={{1, 2}, {2, 3}, {2, 4}, {4, 5},{3, 6}}; int vertexValues[] ={1, 2, 3, 4, 5, 6}; แก้ (n, ขอบ, จุดยอด); คืนค่า 0;}

อินพุต

ผลลัพธ์

153 1 2 4 5 6