Задача №111284. Экономия на рейсах (Ц)
Как вы помните, Джонни работает в министерстве финансов одной небольшой страны. По роду службы ему приходится инспектировать отечественные авиакомпании и изучать маршруты, которые те предлагают.
В стране есть n городов. По государственным законам авиакомпания должна предоставлять услуги двустороннего перелёта между некоторыми парами городов, причём в целях унификации и стандартизации продолжительность любого полёта должна составлять ровно один день.
Авиакомпания называется крупной, если с помощью рейсов этой компании можно добраться из любого города страны до любого другого. Крупная авиакомпания называется экономной, если при этом количество маршрутов, ею предлагаемое, минимально возможное, которое может быть у крупной компании.
Государственная антимонопольная служба возбудила расследование против крупной авиакомпании «Aero-float». Ей предъявлено обвинение в излишней неэкономности. Джонни было поручено проинспектировать «Aero-float» в целях обнаружения финансовых махинаций, но авиакомпания отказалась раскрывать полный список предоставляемых ею прямых рейсов. После продолжительных переговоров руководство компании согласилось сообщить Джонни информацию о минимально возможном количестве перелётов между каждой парой городов, если использовать только прямые рейсы «Aero-float».
Используя эту информацию, помогите Джонни установить, может ли компания «Aero-float» быть экономной или нет? Более формально, установите, существует ли набор рейсов, при котором число рейсов в кратчайших маршрутах именно такие, как было сообщено Джонни, и при котором компания является экономной?
В первой строке содержится единственное целое число n (2 ≤ n ≤ 250) — количество городов в стране.
Далее идёт n строк, содержащих по n целых чисел Ti, j: j-е число в i-й строке равняется минимальному количеству перелётов, требуемому на перемещение из i-го города в j-й.
Гарантируется, что предоставленная информация корректна, то есть существует некоторый набор рейсов, который соответствует данному набору чисел Ti, j.
Выведите «YES», если компания «Aerofloat» может являться экономной, или «NO» в противном случае.
5
0 2 1 1 1
2 0 1 3 3
1 1 0 2 2
1 3 2 0 2
1 3 2 2 0
YES
4
0 1 1 1
1 0 2 2
1 2 0 1
1 2 1 0
NO
Для первого примера ниже приведён возможный вариант предлагаемых компанией маршрутов, при котором она является экономной. На рисунке соединены те пары городов, между которыми есть прямые рейсы.
