Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

کم‌تر رنگ‌آمیزی

گراف جهت‌دار ساده‌ی G با n ‌ راس داده شده است. می‌خواهیم یک رنگ‌آمیزی معتبر از {1,,k} برای راس‌های G بیابیم که k از طول (تعداد راس‌های) بزرگ‌ترین مسیر جهت‌دار در G بیش‌تر نباشد.

ورودی

در اول فایل ورودی عدد n(1n104) و در n‌ سطر بعدی ماتریس مجاورت G آمده است.

خروجی

در فایل خروجی در صورت وجود، عدد نسبت داده شده به هر راس را با یک فاصله بنویسید. در غیر این صورت پیغام Impossible را در فایل خروجی بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

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

پاسخ


ابزار صفحه