Masala #0943

Logistikada ham, kam emas hollarda muammolariga yechimni dasturlash va algoritmlar orqali topib berish mumkin. Quyidagi muammoga ham yechim topib ko`ring.

Bir mamlakatda \(N\) ta shahar va har bir shaharlarni o`zaro bog`lovchi bir tomonlama yo`llar mavjud. Har bir yo`l o`z kengligiga ega. Logistika firmasining yangi loyihasiga ko`ra, bu davlatda har bir shahardan barcha boshqa shaharlarga yuk mashinalari mahsulotga to`ldirilib jo`natiladi.

Muammo shundaki, sig`imi \(x\) miqdorli mahsulot olib o`tadigan yuk mashinasi, \(y\) kenglikdagi yo`ldan o`tishi uchun, \(x \leq y\) shart bajarilishi shart. Ammo firmaning ustaviga ko`ra barcha yuk mashinalarini bir xil sig`imda bo`lishi lozim.

Ushbu mamlakatda firma har bir shahardan boshqa ixtiyoriy shaharga yuk mashinasi orqali mahsulot olib o`ta olish sharti bilan yuk mashinalarining eng katta sig`imini toping.

Yagona qatorda bitta butun son \(N(1 \leq N \leq 300)\) kiritiladi.

Keyingi \(n\) ta qatorning har birida \(N\) tadan natural son - o`lchami \(N\) bo`lgan butun sonlardan iborat kvadrat matritsa kiritiladi. Matritsadagi \(i\)-ustun, \(j\)-qatorda joylashgan son, \(i\)-shahardan \(j\)-shaharga boruvchi yo`lning kengligi kiritladi.

Yagona qatorda bitta butun son ushba mamlakatda firma loyihasini o`tkazishi mumkin bo`lgan yuk mashinalarining eng katta sig`imini chiqaring.