الگوریتمستان - مسئله بشکه‌های آب

$n$ بشکه آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود است که با عدد یکتا بین 1 تا $n$ شماره‌گذاری شده است. $i$-امین لوله بشکه $ x_i $ و $y_i$ را به هم متصل می‌کند. یک سر این لوله در ارتفاع $h_i$ متر به بشکه $ x_i $ متصل است و سر دیگر آن در همان ارتفاع به بشکه $y_i$ متصل است. در زمان صفر بشکه‌ها خالی هستند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت در بشکه شماره یک می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.

شما باید برای هر بشکه اولین زمانی را حساب کنید که آب وارد آن می‌شود.

  

ورودی برنامه

  [برگرد بالا]

در سطر اول ورودی عدد صحیح $T$، تعداد ورودی‌ها آمده است. پیش از هر ورودی، یک سطر خالی آمده است. برای هر ورودی در یک سطر ورودی اعداد $n$، نشان‌دهنده تعداد بشکه‌ها و $m$ نشان‌دهنده تعداد لوله‌ها را بخوانید. سپس در $m$ سطر بعدی در هر سطر اعداد $x_i$، $y_i$ و $h_i$ آمده است که به ترتیب نشان‌دهنده بشکه دو سر لوله $(x_i \neq y_i)$ و ارتفاع نقطه اتصال هر انتهای آن است. می‌دانیم برای هر بشکه زمانی وجود دارد که آب وارد آن بشکه می‌شود.

متغیرها به صورت $ 1 \leq T \leq 100 $ ، $ 1 \leq n \leq 1000 $ ، $ n - 1 \leq m \leq 1000 $ و $ 1 \leq h_i \leq 10^6 $ محدود بوده و $h_i$-ها متمایز از یکدیگر هستند.

  

3

  

2   1

1   2   10

  

3   2

1   2   10

2   3   20

  

3   3

1   2   10

2   3   20

1   3   15

  

خروجی برنامه

  [برگرد بالا]

به ازای هر ورودی، ابتدا یک سطر شامل ":Case #x" بنویسید که در آن x نشان‌دهنده شماره ورودی است، با شروع از عدد 1. در سطر بعدی $n$ عدد را با فاصله از هم چاپ کنید. $i$-امین عدد زمانی است که آب برای اولین بار وارد بشکه $i$ می‌شود.

  

Case #1:

0   10

Case #2:

0   10   40

Case #3:

0   10   30

  

منبع: مرحله انتخابی مسابقات برنامه‌نویسی بیان 1393، مسئله بشکه‌های آب (Water Barrels)

  

حل مسئله

  [برگرد بالا]

در حالت کلی روند جریان آب و پر شدن بشکه‌ها بر اساس قوانین فیزیکی بوده و راهکار حل مسئله شبیه‌سازی روند به صورت گام به گام با در نظر گرفتن این قوانین است. یک شبیه‌سازی می‌تواند به صورت ساعت به ساعت (تغییر به ازای ورود هر متر مکعب آب) باشد که در هر تکرار سطح آب بشکه‌ها مشخص شده و هر گام بر اساس گام قبلی محاسبه می‌گردد. اما چنین راهکاری چه از نظر زمان پیاده‌سازی و چه از نظر زمان اجرا مقرون به صرفه نیست. به ویژه آنکه در حل مسئله نیاز به آگاهی از سطح آب بشکه‌ها در زمان‌های مختلف نداریم و تنها باید زمان شروع پر شدن بشکه‌ها مشخص گردد. یک شبیه‌سازی دیگر می‌تواند بر اساس لحظه رسیدن سطح آب یک بشکه به یک لوله (مستقل از میزان زمان مورد نیاز) باشد. در این حالت حداکثر $m$ گام محاسباتی برای رسیدن به جواب نیاز است. در ادامه منظور از بشکه‌های فعال بشکه‌هایی هستند که جریان آب به آنها رسیده است. همچنین منظور از لوله فعال لوله‌هایی هستند که آب در آنها جریان دارد. بدیهی است که در ابتدای کار تمامی بشکه‌ها و لوله‌ها غیرفعال هستند و با شروع جریان آب بشکه شماره یک به بشکه فعال تبدیل می‌شود.

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

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

بر اساس توضیحات مسئله می‌توان از زمان انتقال آب بین دو سر لوله‌ها صرف نظر کرد. بنابراین لحظه ورود آب به یک بشکه غیرفعال زمانی است که سطح آب بشکه قبلی به ارتفاع لوله متصل به این بشکه می‌رسد. در چنین شرایطی به طور حتم ارتفاع سطح آب در تمام بشکه‌های فعال برابر ارتفاع این لوله یا بیشتر از آن است (چرا؟). پس اگر بشکه فعالی با سطح آب کمتر از این لوله موجود باشد، باید زمان مورد نیاز برای هم‌سطح شدن آن با ارتفاع این لوله را به زمان شروع پر شدن بشکه جدید اضافه کرد.

با توجه به توضیحات ارائه شده اگر گراف $G=(V,E) $ را معادل شبکه بشکه‌ها، $W$ را مجموعه گره‌های معادل بشکه‌های فعال، $H_i$ را ارتفاع سطح آب در بشکه $v_i$ و $t_i$ را زمان ورود آب به بشکه $v_i$ در نظر بگیریم، الگوریتم حل مسئله به این ترتیب خواهد بود:

0- گره $v_1$ را به $W$ اضافه کن و مقدار $t$ (زمان سپری شده) را برابر صفر قرار بده.

1- مراحل 2 تا 4 را تا زمانی که $ V-W $ تهی نیست تکرار کن.

2- یال $e_s$ با کمترین وزن را که گره $ v_s \in V - W $ را به گرهی از $W$ متصل می‌کند انتخاب و $ v_s $ را به $W$ اضافه کن.

3- به ازای هر $v_i \in W $ اگر رابطه $ H_i < \vert e_s \vert $ برقرار باشد (ارتفاع سطح آب بشکه‌ فعال i از ارتفاع لوله $ e_s $ کمتر باشد) مقدار $ \vert e_s \vert - H_i $ (زمان لازم برای بالا آمدن سطح آب تا ارتفاع لوله $e_s$) را به $ t $ اضافه کرده و $H_i$ را برابر $ \vert e_s \vert $ قرار بده.

4- مقدار $ t $ را (به عنوان زمان سپری شده تا شروع جاری شدن آب در بشکه $v_s$) در $ t_s $ قرار بده.

در شروع اجرای این الگوریتم مجموعه $ W $ تهی بوده و مقادیر $ H_i $ و $ t_i $ برای هر بشکه صفر هستند. در طی هر تکرار بند 2 بشکه بعدی انتخاب شده (مشابه الگوریتم پریم) و با تکرارهای بند 3 مقدار $t$ به عنوان زمان جاری بودن آب پیش از رسیدن به این بشکه و ارتفاع جدید آب در بشکه‌های فعال قبلی به روز رسانی می‌شوند. در انتهای اجرای الگوریتم $ t_i $-ها پاسخ مسئله هستند.

پیاده‌‌سازی ساده این الگوریتم از مرتبه $O(n^2m)$ است (چرا؟) که با توجه به محدودیت‌های مقادیر $n$ و $m$ در زمان قابل قبولی خروجی مطلوب را تولید می‌کند.