افزایش ظرفیت خیابانها

شهرداری یک شهر در صدد است برای کاهش ترافیک بین دو منطقه‌ی اصلی شهر (که با تقاطع‌های S و T نشان داده می‌شوند)، ظرفیت بعضی از خیابان‌ها را افزایش بدهد. ظرفیت هر خیابان، با حداکثر تعداد خودروهایی که در دقیقه از آن می‌توان عبور داد مشخص می‌شود (که فرض می‌کنیم یک عدد صحیح است). برای سادگی فرض کنید همه‌ی خیابان‌ها دوطرفه‌اند، ظرفیت یک خیابان در هر دو جهت برابر است، و تقاطع‌ها و خیابان‌ها یک مجموعه‌ی هم‌بند (connected) را تشکیل می‌دهند.

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

به عنوان مثال شکل زیر را در نظر بگیرید. در سمت راست، محل خیابان‌ها و ظرفیت هر خیابان نشان داده شده. شکل سمت چپ یک نحوه‌ی انتقال ترافیک با حداکثر انتقال ممکن بین S و T را نشان می‌دهد. مقدار این حداکثر انتقال ۲۹ خودرو در دقیقه است. یک راه افزایش ظرفیت با شرط افزایش ظرفیت فقط یک خیابان، این است که ظرفیت خیابان بین A و B را به اندازه‌ی ۳ واحد افزایش دهیم. توجه کنید که اگرچه طبق شرایط مسئله می‌توان این ظرفیت را تا ۱۰ واحد افزایش داد، ولی افزایش بیش از ۳، تاثیری در مجموع ظرفیت انتقال بین S و T ندارد. بنابراین پاسخ نهایی ۲۹ + ۳ = ۳۲ است.

. 

فرض کنید حداکثر تعداد خیابان‌ها ۱۰۰۰ و حداکثر ظرفیت هر خیابان ۲۰۰ باشد. برنامه ای بنویسید که خیابان منتخب و مقدار افزایش ظرفیت انتقال بین دو منطقه S و T بعد از افزایش ظرفیت این خیابان را بیابد. m تعداد خیابان‌ها، و C مجموع ظرفیت همه‌ی خیابان‌هاست.

ورودی: در خط اول ورودی یک عدد k<20 نوشته شده که تعداد مجموعه‌های ورودی است. بعد از آن برای هر مجموعه‌ی ورودی، در خط اول n تعداد تقاطع‌ها و m تعداد خیابان‌ها نوشته شده (هر خیابان از یک تقاطع شروع و به یک تقاطع ختم می‌شود، مانند شکل مثال که در آن تقاطع‌ها با دایره نشان داده شده). تقاطع صفر همان S و تقاطع n-1 همان T است. سپس در m خط بعدی، هر خط سه عدد صحیح a, b, c نوشته شده، که دو عدد اول ابتدا و انتهای یک خیابان (a, b <n) و عدد سوم ظرفیت آن خیابان است (c<200).

خروجی: به ازاء هر مجموعه‌ی ورودی دو عدد در یک خط بنویسید که عدد اول مجموع ظرفیت انتقال بین S و T قبل از افزایش ظرفیت یک خیابان و عدد دوم همان مجموع ظرفیت انتقال بعد از افزایش ظرفیت یک خیابان باشد.

ورودی و خروجی نمونه