โปรแกรม C++ หาจำนวนคะแนนสูงสุดที่สามารถลดลงได้จากกราฟ

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

กราฟจะได้รับใน 'ขอบ' ของอาร์เรย์ โดยที่แต่ละองค์ประกอบอยู่ในรูปแบบ {weight, {vertex1, vertex2}}

ดังนั้น หากอินพุตเป็น n =5, m =6, edge ={{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3 , {2, 4}}, {2, {2, 5}}, {1, {3, 5}}} แล้วผลลัพธ์จะเป็น 4

หากเราลบขอบ (1, 2) และ (2, 5) ออกจากกราฟ คะแนนที่ลดลงทั้งหมดจะเป็น 4 และกราฟจะเชื่อมต่อกัน

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

cnum :=0 กำหนดขนาดพาร์ของอาร์เรย์:100. กำหนดขนาดอาร์เรย์ที่มืด:100. กำหนดฟังก์ชัน make() ซึ่งจะใช้เวลา v, par[v] :=v dim[v] :=1 กำหนด ฟังก์ชั่น find() สิ่งนี้จะใช้ v ถ้า par[v] เหมือนกับ v ดังนั้น:return v return par[v] =find(par[v])Define a function unify() สิ่งนี้จะใช้ a, b,a :=find(a)b :=find(b)if a ไม่เท่ากับ b แล้ว:(ลด cnum โดย 1) if dim[a]> dim[b] จากนั้น:สลับค่าของ (a , b) par[a] :=b dim[b] :=dim[b] + dim[a]cnum :=n จัดเรียงขอบอาร์เรย์ตามน้ำหนักขอบสำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต ( เพิ่ม i โดย 1), do:make(i)res :=0for แต่ละขอบในขอบ ทำ:a :=จุดยอดแรกของขอบ b :=จุดยอดที่สองของน้ำหนักขอบ :=น้ำหนักของขอบถ้า find(a) เหมือนกัน เป็น find(b) แล้ว:ถ้าน้ำหนัก>=0 แล้ว:res :=res + 1 * น้ำหนัก ละเว้นส่วนต่อไปนี้ ข้ามไปที่การวนซ้ำถัดไปถ้า cnum เหมือนกับ 1 ดังนั้น:ถ้าน้ำหนัก>=0 แล้ว:res :=res + 1 * weight มิฉะนั้น unif y(a,b)ผลตอบแทน

ตัวอย่าง

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

#include ใช้เนมสเปซ std;int cnum =0;int par[100];int dim[100];void make(int v){ par[v] =v; สลัว[v] =1;}int find(int v){ if(par[v] ==v) return v; return par[v] =find(par[v]);}void unify(int a, int b){ a =ค้นหา (a); b =ค้นหา (b); if(a !=b){ cnum--; if(dim[a]> dim[b]){ สลับ (a, b); } พาร์[a] =b; สลัว[b] +=สลัว[a]; }}int แก้ (int n, int m, เวกเตอร์ >> ขอบ){ cnum =n; เรียงลำดับ(edges.begin(), edge.end()); for(int i =1; i <=n; i++) make(i); ความละเอียดภายใน =0; สำหรับ (อัตโนมัติ &ขอบ:ขอบ){ int a =edge.second.first; int b =edge.second.second; น้ำหนัก int =edge.first; if(find(a) ==find(b)) { if(weight>=0) res +=1 * น้ำหนัก; ดำเนินต่อ; } if(cnum ==1){ if(weight>=0) res +=1 * น้ำหนัก; } อื่น ๆ { รวม (a, b); } } return res;}int main() { int n =5, m =6; เวกเตอร์ >> ขอบ ={{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}; ศาล<<แก้ (n, m, ขอบ); คืนค่า 0;}

อินพุต

ผลลัพธ์

4