Şəbəkə Diversantı
Universitet şəbəkəsi N kompüterdən ibarətdir. Sistem administratorları, düyünlər arasındakı trafik məlumatlarını toplayaraq, şəbəkəni iki alt şəbəkəyə bölməklə aralarındakı trafiki minimuma endirməyə çalışıblar.
Universitetdən qovulduqdan sonra narazı qalan kompüter elmləri tələbəsi Vasya intiqam almağa qərar verir. O, universitet şəbəkəsinə sızaraq kompüterləri yenidən təyin etməklə iki alt şəbəkə arasındakı trafiki maksimuma çatdırmağa çalışır.
Təəssüf ki, Vasya belə bir ən pis bölünməni hesablamağın, tələbə olduğu üçün həll edə bilmədiyi problemlərdən biri olduğunu başa düşür. Buna görə də, o, daha uğurlu bir kompüter elmləri tələbəsi olaraq sizdən kömək istəyir.
Trafik məlumatları C matris şəklində verilir, burada C_ij i-ci və j-ci düyünlər arasında göndərilən məlumatın miqdarını göstərir (C_{ij }= C_ji, C_{ii }= 0). Məqsəd, şəbəkə düyünlərini iki ayrı alt dəstəyə A və B bölərək cəmi maksimuma çatdırmaqdır.
Giriş verilənləri
Giriş faylının ilk sətri düyünlərin sayını N (2 ≤ N ≤ 20) ehtiva edir. Sonrakı N sətir, hər biri N boşluqla ayrılmış tam ədəd ehtiva edən, trafik matrisi C (0 ≤ C_ij ≤ 10000) təmsil edir.
Çıxış verilənləri
Çıxış faylı tək bir tam ədəd ehtiva etməlidir — alt şəbəkələr arasındakı maksimum trafik.