UT-alg-S94-CA4 افزایش ظرفیت خیابان‌ها
Time Limit: 5 Seconds Memory Limit: 32768 KB
شهرداری یک شهر در صدد است برای کاهش ترافیک بین دو منطقه‌ی اصلی شهر (که با تقاطع‌های S و T نشان داده می‌شوند)، ظرفیت بعضی از خیابان‌ها را افزایش بدهد. ظرفیت هر خیابان، با حداکثر تعداد خودروهایی که در دقیقه از آن می‌توان عبور داد مشخص می‌شود (که فرض می‌کنیم یک عدد صحیح است). برای سادگی فرض کنید همه‌ی خیابان‌ها دوطرفه‌اند، ظرفیت یک خیابان در هر دو جهت برابر است، و تقاطع‌ها و خیابان‌ها یک مجموعه‌ی هم‌بند (connected) را تشکیل می‌دهند. به علت محدودیت‌های بودجه، شهرداری فعلا ظرفیت فقط یک خیابان را می‌تواند افزایش دهد و این افزایش ظرفیت حداکثر به‌اندازه‌ی ظرفیت فعلی آن خیابان است (یعنی ظرفیت آن یک خیابان منتخب بعد از افزایش حداکثر دوبرابر ظرفیت قبلی خواهد بود). به عنوان مثال شکل زیر را در نظر بگیرید. در سمت راست، محل خیابان‌ها و ظرفیت هر خیابان نشان داده شده. شکل سمت چپ یک نحوه‌ی انتقال ترافیک با حداکثر انتقال ممکن بین S و T را نشان می‌دهد. مقدار این حداکثر انتقال ۲۹ خودرو در دقیقه است. یک راه افزایش ظرفیت با شرط افزایش ظرفیت فقط یک خیابان، این است که ظرفیت خیابان بین A و B را به اندازه‌ی ۳ واحد افزایش دهیم. توجه کنید که اگرچه طبق شرایط مسئله می‌توان این ظرفیت را تا ۱۰ واحد افزایش داد، ولی افزایش بیش از ۳، تاثیری در مجموع ظرفیت انتقال بین S و T ندارد. بنابراین پاسخ نهایی ۲۹ + ۳ = ۳۲ است.
الف) [۱۰ نمره‌ی اختیاری] با فرض این‌که ظرفیت همه‌ی خیابان‌های شهر داده شده. الگوریتمی طراحی کنید که در زمان O(m3 C)، خیابان منتخب و مقدار افزایش ظرفیت انتقال بین دو منطقه S و T بعد از افزایش ظرفیت این خیابان را بیابد. m تعداد خیابان‌ها، و C مجموع ظرفیت همه‌ی خیابان‌هاست. همچنین نشان دهید الگوریتمی هم وجود دارد که در زمان O(m2C) این مسئله را حل می‌کند. ب) [۴۰ نمره‌ی پیاده‌سازی] فرض کنید حداکثر تعداد خیابان‌ها ۱۰۰۰ و حداکثر ظرفیت هر خیابان ۲۰۰ باشد. یکی از الگوریتم‌های فوق را که به نظرتان، با توجه به حدکثر اندازه‌ی ورودی، مناسب است پیاده‌سازی کنید. برنامه‌ی شما باید در کم‌تر از ۲ ثانیه (روی سامانه‌ی شیرکد) برای بزرگ‌ترین داده ورودی پاسخ را بیابد. [راهنمایی: اگر به مشکل زمان اجرا برخوردید، توجه کنید که لازم نیست همه‌ی یال‌ها را برای افزایش ظرفیت امتحان کنید. همچنین لازم نیست که هر بار از صفر جریان را حساب کنید.] ورودی: در خط اول ورودی یک عدد k<20 نوشته شده که تعداد مجموعه‌های ورودی است. بعد از آن برای هر مجموعه‌ی ورودی، در خط اول n تعداد تقاطع‌ها و m تعداد خیابان‌ها نوشته شده (هر خیابان از یک تقاطع شروع و به یک تقاطع ختم می‌شود، مانند شکل مثال که در آن تقاطع‌ها با دایره نشان داده شده). تقاطع صفر همان S و تقاطع n-1 همان T است. سپس در m خط بعدی، هر خط سه عدد صحیح a, b, c نوشته شده، که دو عدد اول ابتدا و انتهای یک خیابان (a, b <n) و عدد سوم ظرفیت آن خیابان است (c<200). خروجی: به ازاء هر مجموعه‌ی ورودی دو عدد در یک خط بنویسید که عدد اول مجموع ظرفیت انتقال بین S و T قبل از افزایش ظرفیت یک خیابان و عدد دوم همان مجموع ظرفیت انتقال بعد از افزایش ظرفیت یک خیابان باشد. ورودی و خروجی نمونه (مجموعه‌ی اول یک ورودی بسیار ساده و دومی معادل مثال بالاست): Output: 10 20 29 32 Input: 2 2 1 0 1 10 9 14 0 1 12 1 2 30 3 0 18 0 4 15 3 1 10 1 5 8 3 5 10 6 4 9 5 6 20 5 7 14 6 7 15 7 8 20 8 2 2 5 8 10