UT-alg-S94-CA1 پهنای باند بیشینه

Time Limit: 3 Seconds    Memory Limit: 65536 KB

برای ارتباط قابل اطمینان شعبه‌های یک شرکت با شعبه‌ی مرکزی، باید پهنای باند مناسبی از طریق شبکه‌ی کشوری خریداری شود. این شرکت دارای n شعبه است که یکی از آن‌ها شعبه‌ی مرکزیست. هر شعبه در یک شهر است و بین بعضی از شهر‌ها، مثلا دو شهر i و j، خط مستقیم با پهنای باند bi,j وجود دارد. هزینه‌ی خرید پهنای باند بین دو شهر ثابت و برای سادگی معادل یک واحد فرض شده است. به بیان دیگر اگر پهنای باند بین دو شهر i و j توسط این شرکت خریداری شود، هزینه‌ی آن یک واحد است و این شرکت از تمام پهنای باند bi,j می‌تواند استفاده کند. شعبه‌ی مرکزی برای ارتباط با شعبه‌های دیگر تنها از پهنای باندی که خریداری شده می‌تواند استفاده کند. پهنای باند یک مسیر برابر حداقل پهنای باند یال‌های آن است. مسئول شبکه‌ی این شرکت باید با صرف کم‌ترین هزینه، به‌ترین ارتباط ممکن را بین شعبه‌ی مرکزی و همه‌ی شعبه‌های دیگر فراهم کند. به‌ترین ارتباط بین دو شعبه، مسیریست که پهنای باند آن بین همه‌ی مسیر‌های بین آن دو شعبه، بیشینه باشد. توجه کنید که هدف اصلی ایجاد به‌ترین ارتباط بین شعبه‌ی مرکزی و بقیه‌ی شعبه‌هاست ولی در عین حال اگر حذف یالی تغییری در این هدف اصلی ایجاد نمی‌کند، به‌تر است از خرید آن صرف نظر شود تا از هزینه‌ی اضافی پر هیز شود.

مثال: در شکل زیر، در سمت چپ همه‌ی شبکه‌ی ارتباطی کشوری با پهنای باند هر ارتباط نشان داده شده است. شعبه‌ی اصلی با دایره‌ی بزرگ‌تر نشان داده شده. در سمت راست یک پاسخ بهینه با کم‌ترین هزینه نشان داده شده است.

الف) نشان دهید، یال‌های انتخاب شده در هر جواب بهینه‌ای، تشکیل یک درخت می‌دهند.

ب) الگوریتمی ارائه کنید که برای یک گراف ورودی یک جواب بهینه برای مسئله‌ی فوق پیدا کند. درستی الگوریتم خود را اثبات و زمان اجرای آن را تحلیل کنید.

(راهنمایی: چه ارتباطی بین این مسئله و الگوریتم‌های حریصانه‌ای که تا به حال دیده‌اید وجود دارد؟)

پ) اگر در الگوریتم قسمت (ب) از داده‌ساختار Heap استفاده کرده‌اید، الگوریتمی بدون Heap طراحی کنید و زمان اجرای آن را با الگوریتم قسمت (ب) مقایسه کنید. اگر در قسمت (ب) از Heap استفاده نکرده‌اید، آیا استفاده از Heap الگوریتم شما را سریع‌تر می‌کند؟ زمان اجرا در هر دو حالت را تحلیل و مقایسه کنید.

ت) نشان دهید پاسخ بهینه‌ای وجود دارد که در آن مسیر بین هر دو شعبه‌ (نه لزوما شعبه‌ی مرکزی و شعبه‌های دیگر)  هم بهینه است. به بیان دیگر، پهنای باند مسیری که هر دو شعبه‌ی دلخواه روی درخت آن پاسخ بهینه دارند، بیش‌ترین پهنای باند ممکن بین همه‌ی مسیر‌های بین آن دو شعبه است (توجه کنید که درخت پاسخ در مثال بالا این خاصیت را ندارد).

ث) الگوریتم قسمت (ب) یا (پ) را با سی‌، سی‌پلاس‌پلاس، یا جاوا پیاده سازی کنید (به زمان اجرا و تعداد شهر‌ها و یال‌ها توجه کنید). برنامه‌ی شما باید داده‌های ورودی را از stdin بخواند و پاسخ را در stdout بنویسد. حداکثر تعداد شهر‌ها ۱،۰۰۰ و حداکثر تعداد یال‌ها ۱۰۰،۰۰۰ است و برنامه‌ی شما باید در کم‌تر از ۵ ثانیه (بر روی کارگزار Share Code) پاسخ را بیابد. قالب ورودی و خروجی باید به شکل زیر باشد:

ورودی: خط اول، n تعداد شهرها (رئوس) و m تعداد خطوط ارتباطی بین آن‌ها (یال‌ها). بعد از آن در m خط بعدی، در هر خط سه عدد برای دو سر یک یال و پهنای باند آن داده شده (می‌توانید فرض کنید که ورودی بدون اشکال است و یک مجموعه‌ی هم‌بند را تشکیل می‌دهد). شماره‌ی شهر‌ها از صفر تا n-1 است و شعبه‌ی اصلی در شهر صفر قرار دارد. پهنای باند یک یال حداکثر ۱،۰۰۰،۰۰۰ است.

خروجی: تنها یک خط شامل کم‌ترین پهنای باندی که در جواب بهینه استفاده شده.

Input

ورودی: خط اول، n تعداد شهرها (رئوس) و m تعداد خطوط ارتباطی بین آن‌ها (یال‌ها). بعد از آن در m خط بعدی، در هر خط سه عدد برای دو سر یک یال و پهنای باند آن داده شده (می‌توانید فرض کنید که ورودی بدون اشکال است و یک مجموعه‌ی هم‌بند را تشکیل می‌دهد). شماره‌ی شهر‌ها از صفر تا n-1 است و شعبه‌ی اصلی در شهر صفر قرار دارد. پهنای باند یک یال حداکثر ۱،۰۰۰،۰۰۰ است.

Output

خروجی: تنها یک خط شامل کم‌ترین پهنای باندی که در جواب بهینه استفاده شده.

Sample Input

6 9
0 1 9
2 1 18
2 0 9
2 3 6
3 4 10
4 2 12
4 5 12
5 0 3
0 3 8

Sample Output

9

Submit