المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:تئوری نهایی سوم:سوال ۲

سوال ۲

تعداد ‎$n$‎ شهر و ‎$e$‎ جاده بین آن‌ها داده شده است. جاده‌ها یک طرفه هستند و هر جاده وزنی دارد که برابر ماکسیمم باری است که از طریق آن جاده می‌توان منتقل کرد. بیشترین باری که بین دو شهر ‎$u$‎ و ‎$v$‎‌ می‌توان منتقل کرد برابر ماکسیمم وزن جاده‌ها با مینیمم وزن بین تمام مسیرهای بین این دو شهر است. الگوریتمی از ‎$O(ne+n^2) $‎ ارایه دهید که این مقدار را برای تمام جفت شهرها بدست آورد‎.


ابزار صفحه