Borcların tərcüməsi#11525
Təsəvvür edin ki, dostlarınız arasında üç nəfər var: , və . Bu vəziyyətdə , -yə rubl borcludur, isə -yə rubl borcludur. Ümumi borc məbləği rubldur. Göründüyü kimi, bu borclar ən optimal şəkildə təşkil olunmayıb. Borcları aşağıdakı kimi yenidən paylayaq: qoy , -yə rubl borclu olsun və heç kimə borclu olmasın. Borcların mənası dəyişməyib, lakin bütün borcların cəmi rubl olub.
Bu məsələ təsvir olunan nümunəni ümumiləşdirir. Təsəvvür edin ki, dostlarınız arasında nəfər var və insanlar arasında borclar məlumdur. Verilən borcları optimallaşdırın, onların mənasını dəyişmədən. Başqa sözlə, nəticədə hər bir insan üçün nə qədər borclu olduğu və nə qədər almalı olduğu arasındakı fərq saxlanılmalıdır. Borcların optimal paylanmasında bütün borcların minimal cəmini tapın. Məsələnin daha yaxşı başa düşülməsi üçün test nümunələrinin izahına baxın.
Birinci sətirdə iki tam ədəd və m~(1 \le n \le 100;~ 0 \le m \le 10^4) verilib. Növbəti sətirdə borclar təsvir olunub. -ci sətirdə üç tam ədəd a_i, b_i, c_i ~(1 \le a_i, b_i \le n;~ a_i \ne b_i;~ 1 \le c_i \le 100) verilib, bu o deməkdir ki, a_i insanı b_i insanına c_i rubl borcludur.
İnsanların -dən -ə qədər tam ədədlərlə nömrələndiyini qəbul edin.
Zəmanət verilir ki, eyni insan cütü giriş məlumatlarında bir dəfədən çox rast gəlinmir. Giriş məlumatlarında eyni zamanda və insan cütü rast gəlinmir.
Yeganə tam ədəd çıxarın — borcların optimal paylanmasında minimal cəmi.
Birinci nümunədə, nömrəli insanın nömrəli insana rubl, nömrəli insana rubl və nömrəli insana rubl borclu olduğunu qəbul edə bilərik. Başqa heç kim heç kimə borclu deyil. Nəticədə ümumi borc olur.
İkinci nümunədə heç bir borc yoxdur.
Üçüncü nümunədə bütün borcları ləğv etmək olar.
Nümunə 1
Nümunə 2
Nümunə 3