المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۵۷

Network

شما تعدادی رایانه دارید که می‌خواهید با استفاده از کابل آن‌ها را به‌هم وصل کنید‎.‎

برای اتصال همه رایانه‌ها به یکدیگر کافیست هر دو رایانه بتوانند با استفاده از یک مسیر به هم ارتباط برقرار کنند. به ازای هر دو رایانه اندازه کابلی که لازم است تا آن ها را به هم متصل کنیم را داریم‎.‎

ما فقط دو نوع کابل نوع ‎$0$‎ و نوع ‎$1$‎ داریم ، که هزینه هر متر آن‌ها به ترتیب ‎$p_0$‎ و ‎$p_1$‎ است و از هر کدام به ترتیب ‎$q_0$‎ و ‎$q_1$‎ متر در بازار موجود است. همچنین هر کابلی که دو رایانه را به هم متصل می کند باید کاملاً از یک نوع باشد‎.

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

ورودي

  • در سطر اول ورودی دو عدد ‎$1 \leq n \leq 10^3$‎ و ‎$1 \leq m \leq 10^4$‎ نشان‌دهنده تعداد رایانه‌ها و تعداد جفت رایانه‌هایی که می‌توان آن‌ها را با سیم مستقیماً به‌هم متصل کرد، آمد است‎.‎
  • در ‎$m$‎ سطر بعد در هر سطر سه عدد ‎$1 \leq a_i,b_i \leq n$‎ و ‎$ 0 \leq c_i \leq 100$‎ آمده است که نشان می‌دهد می‌توان دو رایانه ‎$a_i$‎ و ‎$b_i$‎ را با کابل به اندازه ‎$c_i$‎ به‌هم متصل کنیم‎.‎
  • در سطر آخر ورودی چهار عدد ‎$1 \leq p_0 وq_0,p_1 وq_1 \leq 10^5$‎ به ترتیب آمده است.

خروجي

در تنها سطر خروجی پاسخ سؤال را چاپ نمایید، در صورتی که این کار امکان‌پذیر نیست در خروجی ‎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)$‎ حل میشود.


ابزار صفحه