Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

گراف وزن‌دار

گراف جهت‌دار G=(V,E) داده شده است. روی یال (i,j) که راس i‌را به j‌وصل می‌کند عددی صحیح به عنوان وزن آن یال نوشته شده است.

راس uV و یال‌های متصل به آن را در نظر بگیرید. عمل Transfer(u,d) یعنی این که از وزن کلیه‌ی یال‌های ورودی این راس عدد صحیح d (مثبت یا منفی) را کم کرده، به وزن کلیه‌ی یال‌های خروجی آن عدد d را اضافه کنیم. می‌خواهیم این اعمال را به ترتیبی انجام دهیم که کلیه‌ی مقادیر روی یال‌ها مثبت (یعنی بزرگ‌تر از صفر) شوند.

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

ورودي

د رسطر اول فایل ورودی تعداد رئوس و تعداد یال‌ها و در سطرهای بعد، در هر سطر شماره‌ی رئوس ابتدا و انتها و وزن یکی از یال‌ها نوشته شده است. فرض کنید گراف‌ ساده است و تعداد رئوس آن حداکثر ۱۰۰ است.

خروجي

در هر یک از سطرهای فایل خروجی دو عدد u و d ( اول u و سپس d) نوشته می‌شوند که نشان‌دهنده‌ی عمل Transfer(v,d) هستند. در صورتی که مسئله جواب ندارد، پیغام NO SOLUTION را در فایل خروجی چاپ کنید.

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

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

ابزار صفحه