گراف جهتدار G=(V,E) داده شده است. روی یال (i,j) که راس iرا به jوصل میکند عددی صحیح به عنوان وزن آن یال نوشته شده است.
راس u∈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 |