المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۲:سوال ۴

انتخاب باحال

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

ورودی

فایل‌های ورودی $Graphx.in$ می‌باشند ($0\Leftarrow x \Leftarrow 9$). در این ۱۰ فایل ابتدا تعداد رئوس و تعداد یال‌ها آمده‌اند. سپس در سطر بعد به ازای هر راس عدد نسبت داده شده به آن راس آمده است. در سطر‌های بعدی هر سطر دو راس انتهایی یک یال را مشخص می‌کند. به شما این ۱۰ فایل در ابتدای امتحان داده می‌شود.

در فایل خروجی ابتدا تعداد رئوس انتخاب شده را بنویسید. سپس در سطر بعد شماره‌ی رئوس انتخاب شده را درج نمایید. شما باید ۱۰ فایل $Graph0.out$ تا $Graph9.out$ را که هر یک، خروجی متناظر با فایل‌ هم نام ورودی هستند، در انتهای امتحان تحویل دهید.

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

ورودي نمونه خروجي نمونه
5 4
0 2 1 1 0
1 2
2 5
3 5
4 5
2
5

ابزار صفحه