المپدیا

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

ابزار کاربر

ابزار سایت


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

گراف وزن‌دار

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

راس $u \in V$ و یال‌های متصل به آن را در نظر بگیرید. عمل $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‎

ابزار صفحه