[ UVa ] 11228 - Transportation system

আমাদের কে গ্রফল্যান্ডের শহরগুলির যে co-ordinate দেয়া থাকবে তাদের সবগুলি থেকে সবগুলির দূরত্ব বের করে সেটা কে ওয়েট ধরে একটা গ্রাফ বানাতে হবে ।
এই গ্রাফ থেকে MST বের করেত হবে ।
আমাদের মূল গ্রাফ থেকে MST বের করার সময় যখন প্রতিবার একটা করে নতুন এজ নিব তখন চেক করতে হবে নতুন এজটার ওয়েট আমাদের Threshold ( r ) থেকে বড় কি না ?
যদি সেটা r থেকে বড় হয় তবে সেই এজটা ওয়েট rail roads extension এ যোগ করতে হবে । আর যদি সেটা r থেকে ছোট হয় তবে সেটা state roads extension এ যোগ করতে হবে ।
মোট states সংখ্যা = mst তে মোট node সংখ্যা - মোট এজ সংখ্যা [ rail road এজ বাদে ]
প্রিন্ট Extension rounded to the nearest integer ;)

কোড :

হ্যাপি কোডিং :D

কম্পিউটার বিজ্ঞান