المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۱۴

عبارت جمع

گراف کامل $n$‌ راسی $G$ را در نظر بگیرید. راس $i$ ام این گراف دارای ارزش $v_i$ است. هدف مسئله یافتن زیرگراف $H$ از $G$ است که همبند بوده و دارای $m$ یال باشد وا گر درجه‌ی راس $i$ در $H$ را با $d_i$ نشان بدهیم، کمیت $\sum_{i=1}^n$ بیشینه شود.

ورودی

در خط اول فایل ورودی $n$ و $m$ آمده است. سپس در یک خط به‌ترتیب اعداد $x_1$، $x_2$، … و $v_n$ نوشته شده‌اند. همه‌ی عددهای ورودی، عددهای طبیعی بین ۱ و ۱۵۰ هستند.

خروجی

جواب مسئله را در فایل خروجی بنویسید. این فایل باید شامل $n-1$ خط باشد و در آن نیمه‌ی پایین ماتریس مجاورت $H$ بیاید. فرض کنید مسئله جواب دارد.

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

ورودي نمونه خروجي نمونه
5 6
100 50 5 40 10
1
1 0
1 1 0
1 1 0 0

ابزار صفحه