المپدیا

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

ابزار کاربر

ابزار سایت


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

تخصیص برچسب

گراف وزن‌دار و جهت‌دار $G$ به ما داده شده ولی وزن تعدادی از یال های آن مشخص نیست هدف مسئله این است که تعدادی عدد داده شده را طوری به یال‌ها‌ی گراف به عنوان وزن نسبت دهیم که وزن کم‌وزن‌ترین دور گراف کمینه شود.

ورودي

در سطر اول فایل ورودی تعداد رئوس گراف و بعد از آن یک جدول $n\times n$ داده شده است به طوری که اگر در گراف بین دو راس $i$ و $j$‌یال نباشد $a_{i,j}$ برابر ۰ است. اگر یال بدون وزن باشد برابر $-1$ و در غیر این صورت برابر وزن یال بین دو راس می‌باشد. در سطر آخر هم به تعداد یال‌های بدون وزن عدد آمده است. (وزن‌ها عدد طبیعی و کوچک‌تر از ۳۲۰۰۰ هستند و تعداد راس‌ها از ۱۵۰ بیش‌تر نیست. همچنین تعداد یال‌های بدون برچسب حداکثر ۲۰ می‌باشد)

خروجي

در سطر اول فایل خروجی وزن کم‌وزن‌ترین دور و در سطر بعد دنباله‌ی راس‌های تشکیل‌دهنده‌ی دور و در سطر آخر هم وزن یال‌ها به ترتیب آمده است. هر عدد را حداکثر به یک یال می‌توان نسبت داد.

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

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

ابزار صفحه