Skip to main content

[ UVa ] 10600 - ACM Contest and Blackout

  • এই সমস্যা তে আমাদের কে 2nd best MST বের করেত হবে । 
  • এই সমস্যা সমাধান করার জন্য আমাদের কে প্রথমে MST বের করতে হবে । এবং এই MST তে যে এজ গুলি নেয়া হয়েছে সেগুলো ইন্ডিকেট করে রাখতে হবে । 
  • এখন এই MST এর এজগুলি থেকে প্রতিবার একটা করে এজ বাদ দিয়ে নতুন MST গঠন করার চেষ্টা করবো । এবং সেটার মোট খরচ কত হয় সেটা হিসাবে করে রাখব । 
  • আমরা যখন আমাদের MST থেকে কোন এজ বাদ দিয়ে নতুন একটা ST বানাতে চেষ্টা করবো তখন শেষে আমাদেরকে চেক করতে হবে যে এই এজ টি বাদ দিয়ে আসলেই MST বানানো সম্ভব কি না ? 
  • এটা নিশ্চিত করার জন্য যখন আমাদের MST বানানো শেষ হবে তখন দেখতে হবে যে আমাদের সবগুলি নোড একই সেটের মধ্যে আছে কি না ?
  • যদি সবগুলি একই সেটের মধ্যে না থাকে তবে বুঝতে হবে । আমরা যে এজ কে বাদ দিয়ে MST বানানোর চেষ্টা করেছি । সেই এজ কে বাদ দিয়ে আসলে MST বানানো সম্ভব না ।
  • এই ভাবে যতগুলো MST গঠন করা যাবে তাদের মধ্যে যেটার খরচ সবচেয়ে কম সেটাই আমাদের 2nd best Minimum Spanning Tree .  
কোড :

Happy Coding :)

Comments

Popular posts from this blog

[ UVa ] 11463 - Commandos

এই সমস্যা টা মিনি-ম্যাক্স টাইপের সমস্যা ।  এই সমস্যা সমাধান করার জন্য প্রথমে আমাদের কে প্রত্যেক বিল্ডিং থেকে প্রত্যেক বিল্ডিং এ যাওয়ার মিনিমাম পাথ বের করতে হবে এই জন্য আমরা Floyd Warshall ব্যবহার করতে পারি ।  এর পর আমাদের কে যে source ও destination দেয়া থাকবে ।  আমরা প্রত্যেক বার source থেকে i হয়ে destination এ যেতে চেষ্টা করবে । যদি আমরা যতগুলি i ব্যবহার করে আমাদের লক্ষ্যে যেতে পারব তাদের মধ্যে যেটা ম্যাক্সিমাম সেটাই আমাদের কে প্রিন্ট করতে হবে ।   কোড :