Airports

توسط علیرضا رضایی نیا

ارسال شده در
1397-03-03

Airports

شرح سوال


امروز میخواهیم به سوال Airports (uva 11733) بپردازیم ...ماهیت سوال این است که میگه ما چند تا شهر داریم میخواهیم از هر شهر به فرودگار راه داشته باشیم . بعد هزینه ی ساخت فرودگاه و هزینه ی ساخت راه ها هم به شما میده . یک شهر وقتی به فرودگاه راه داره که یا فرودگاه داخل اون شهر احداث بشه یا از طریق راه به شهری ک فرودگاه داره متصل بشه . خیله خب سمال از ما میخواهد مینیمم هزینه داشته باشیم و هر شهر به فرودگاه راه داشته باشه. الگوریتم عملا همون کراسکال هستش فقط با چند خط اضافه تر ! . شما باید سورت کنید راه ها رو ترتیب کوچک به بزرگ. بعد پیمایش کنید راه ها رو و بگید آیا این راهی که میخوام احداث کنم از هزینه ی ساخت فرودگاه کمتره یا نه اگه کمتر بود که راه را میسازیم اگه کمتر نبود راه را نمیسازیم.سپس تعداد روت (پدر اصلی) ها را میشماریم که تعداد روت تعداد فرودگاه هایی است که باید احداث شود.


توضیحات


سطح سوال لینک سوال
متوسط Airports

کد حل سوال


حل سوال به زبان:
سی پلاس پلاس java وجود ندارد python وجود ندارد

دانلود حل سوال


PDF

تگ ها:
graph
شما برای ارسال نظر باید وارد سایت شوید

جستجو در سایت

به کانال تلگرامی ما بپیوندید