شما تعدادی رایانه دارید که می‌خواهید با استفاده از کابل آن‌ها را به‌هم وصل کنید.
برای اتصال همه رایانه‌ها به یکدیگر کافیست هر دو رایانه بتوانند با استفاده از یک مسیر به هم ارتباط برقرار کنند. به ازای هر دو رایانه اندازه کابلی که لازم است تا آن ها را به هم متصل کنیم را داریم.
ما فقط دو نوع کابل نوع $0$ و نوع $1$ داریم ، که هزینه هر متر آن‌ها به ترتیب $p_0$ و $p_1$ است و از هر کدام به ترتیب $q_0$ و $q_1$ متر در بازار موجود است. همچنین هر کابلی که دو رایانه را به هم متصل می کند باید کاملاً از یک نوع باشد.
شما باید کم‌ترین هزینه‌ای را به دست بیاورید که با استفاده از آن می‌توان رایانه‌ها را به هم متصل کرد.
در تنها سطر خروجی پاسخ سؤال را چاپ نمایید، در صورتی که این کار امکان‌پذیر نیست در خروجی Impossible چاپ کنید.
| ورودي نمونه | خروجي نمونه |
|---|---|
| 6 7 1 2 7 2 6 5 1 4 8 2 3 5 3 4 5 5 6 6 3 5 3 2 11 3 100 | 65 |
پاسخ
ادعا می‌کنیم که یال‌های جواب یک زیردرخت فراگیر کمینه (MST) می‌سازند. بدیهی است که جواب بهینه یک درخت است وگرنه دور دارد و می‌توان یک یال را حذف کرد و هزینه کم‌تر شود. حال ثابت می‌کنیم که جواب بهینه یک MST هم هست. کوتاه‌ترین یالی که در MST آمده و در جواب بهینه‌ی ما نیست را در نظر می‌گیریم و $e$ می‌نامیم. $e$ را به جواب بهینه اضافه کرده و طولانی‌ترین یالی که با $e$ در یک دور قرار دارد را حذف می‌کنیم تا به یک درخت جدید برسیم. بدیهی است که می‌توان درخت جدید را مشابه جواب بهینه با سیم‌ها بپوشانیم، با این تفاوت که به جای اینکه یال حذف شده را بپوشانیم، $e$ را می‌پوشانیم. (طول $e$ کم‌تر از یال حذف شده است زیرا اگر یال حذف شده کوتاه‌تر از e بود در دوری که با $e$ تشکیل داده اند، همه یال‌ها کوتاه تر از $e$ بودند و چون همه یال‌های کوتاه تر از $e$ در MST آمده‌اند در MST اولیه دور داشته‌ایم که تناقض است(! پس اگر با سیم‌های موجود می توانستیم جواب بهینه را سیم‌کشی کنیم درخت جدید را هم می‌توانیم و چون طول $e$ کم‌تر است، هزینه کل درخت جدید از هزینه کل جواب بهینه کم‌تر است که تناقض است پس جواب بهینه یک MST است. پیدا کردن یک MST از $O(e \log n)$ است که می‌توان با الگوریتم‌هایی نظیر kruskal یا prim آن را بدست آورد.
بدون اینکه به کلیت مسئله لطمه وارد شود می‌توان فرض کرد که $p_0< p_1$ است. از آنجا که مجموع طول یال‌های MST ثابت است بدیهی است که در جواب بهینه بیش‌ترین مقدار ممکن که می‌توان را با سیم‌های $p_0$ پوشانده‌ایم و باقی را به ناچار با $p_1$ یعنی بین دو جواب، جوابی که مقدار بیش‌تری از $p_0$ استفاده کرده‌ایم بهتر است. حال مسئله به این تبدیل می شود که $n-1$ شی با اندازه‌های $L_i$ (وزن یال $i$ ام در (MST داریم و می‌خواهیم بیش‌ترین مقدار از آن‌ها (از لحاظ مجموع وزن) را درون یک کیسه با اندازه $q_0$ جا دهیم. این مسئله به knapsack یا مسئله کوله پشتی معروف است که به صورت پویا از $O(q_0 n)$ حل میشود.