======   فوت کوزه‌گری ======



جشن کوزه‌گران در حال برگزاری است و ۱۰۰ کوزه‌گر از کشورهای مختلف در این جشن حضور دارند. هر یک از کوزه‌گرها فوت و فن منحصر به فرد خودش را دارد. **می‌خواهیم همه‌ی کسانی که در جشن شرکت می‌کنند، همه‌ی این ۱۰۰ نوع فن کوزه‌گری را یاد بگیرند.** مشکل این است که کوزه‌گرها زبان‌های مختلفی دارند و حرف همدیگر را متوجه نمی‌شوند. خوشبختانه $n$ مترجم خبره داریم که تمام زبان‌های دنیا را می‌دانند. می‌توانیم تعدادی از آن‌ها را به جشن دعوت کنیم. دعوت از مترجم $i$ ام به مقدار $c_i$ هزینه دارد.
 $(1 \leq i \leq n)$ \\
هر کسی که در جشن فوت و فنی را بلد است یا یاد می‌گیرد، به تمام دوستانش آن فن را یاد می‌دهد. در ابتدا هیچ دو نفری با هم دوست نیستند و هر دو نفری حرف همدیگر را می‌فهمند مگر اینکه هر دوی آن‌ها کوزه‌گر باشند. (مترجمان حرف همه را می‌فهمند و کوزه‌گران فقط حرف مترجمان را می‌فهمند)



**آ.** هر کسی در جشن یک هزینه برای دوستی دارد، هزینه دوستی مترجم $i$ ام 
$w_i^t$
 و هزینه دوستی کوزه گر $i$ ام برابر 
$w_i^k$
 است. در هر مرحله می‌توانیم دو نفر که **حرف همدیگر را می‌فهمند** انتخاب کنیم و این دو را با هزینه‌ای برابر جمع $w$های متناظر این دو نفر، با هم دوست کنیم. الگوریتمی با پیچیدگی زمانی $O(n)$ ارائه کنید که به عنوان ورودی $n$، 
$c_1, c_2, \dots , c_n$ 
و مقادیر 
$w_1^t, w_2^t, \dots , w_n^t$ 
و 
$w_1^k, w_2^k, \dots , w^k_{100}$ 
را بگیرد و کمترین هزینه را برای اینکه همه افراد حاضر در جشن، تمام ۱۰۰ فوت و فن کوزه‌گری را یاد بگیرند، خروجی دهد. (۳۰ امتیاز)



**ب.** در هر مرحله می‌توانیم یک نفر حاضر در جشن مانند $v$ و زیرمجموعه‌ای از افراد حاضر در جشن مانند $S$ را انتخاب کنیم، به طوری که $v \notin S$ و $v$ حرف تمام اعضای $S$ را متوجه شود. سپس با هزینه $Cost(v, S)$ تمام اعضای $S$ را با $v$ دوست کنیم. می‌دانیم تابع $Cost(v, S)$ خاصیت‌های زیر را دارد:
  *  این تابع در زمان $O(|S|)$ قابل محاسبه است.
  * ضمنا این تابع همواره نامنفی است.
  * اگر $S = \emptyset$ (تهی) باشد، $Cost(v, S) = 0$
  * به ازای هر $v$ و هر زیرمجموعه $S_1, S_2$ میدانیم $Cost(v, S_1 \cup S_2) \leq Cost(v, S_1) + Cost(v, S_2)$
  * به ازای هر $v$ و $S_1 \subseteq S_2$ میدانیم: $Cost(v, S_1) \leq Cost(v, S_2)$
الگوریتمی با پیچیدگی زمانی چندجمله‌ای بر حسب $n$ ارائه کنید که به عنوان ورودی عدد $n$ و مقادیر $c_1, \dots , c_n$ را بگیرد و کمترین هزینه را برای اینکه همه افراد حاضر در جشن، تمام ۱۰۰ فوت و فن کوزه‌گری را یاد بگیرند، خروجی بدهد. (می‌توانید در الگوریتم خود از تابع $Cost(v, S)$ استفاده کنید، دقت کنید در این قسمت
برای ایجاد دوستی میان $u$ و $v$ لازم است هم $u$ را در مجموعه $S$ مربوط به $v$ بیاورید و هم $v$ را در مجموعه $S$ مربوط به $u$) (۷۰ امتیاز)



  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]