Задача 059 — Задачи на Графы

В стране $N$ городов. Некоторые пары городов соединены двусторонними авиарейсами, каждый рейс имеет цену, большую 1000 рублей, причём из любого города можно добраться до любого другого (возможно, с пересадками). Компания публикует сборник, в котором для каждой из $N(N-1) / 2$ пар городов указана минимальная цена, которую надо заплатить, чтобы добраться от одного из них до другого; в конце сборника указывается сумма всех этих $N(N-1) / 2$ чисел. В некоторый момент компания уменьшила стоимость одного из рейсов на 1000 рублей. Докажите, что итоговая сумма в новом сборнике будет отличаться от старой не более, чем на $250 N^{2}$ .

Подсказка

Обозначим два города, между которыми уменьшили стоимость рейса, через $X$ и $Y$ . Пусть $A$ — множество городов, из которых после уменьшения дешевле добраться до $X$ , чем до $Y$ , в том числе в множество $A$ входит сам город $X$ . Пусть $B$ множество городов, из которых добраться до $Y$ не дороже, чем до $X$ , в том числе в множество $B$ входит сам город $Y$ . Что будеь если при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ .

Решение

Пусть при проезде самым дешевым путем между городами $U$ и $V$ множества $A$ мы сначала доезжаем из $U$ до $X$ , потом летим из $X$ в $Y$ по удешевленному рейсу, а затем долетаем из $Y$ в $V$ . Тогда, если из $X$ сразу полететь в $V$ по пути наименьшей стоимости, мы заплатим меньшую цену за весь путь: ведь цена перелета между $X$ и $Y$ все равно осталась положительной, и хотя бы эту цену мы сэкономим. Аналогичны рассуждения для двух вершин из множества $B$ . Поэтому путь минимальной стоимости между двумя вершинами одного множества не содержит рейс из $X$ в $Y$ .

Обозначим количество городов в множестве $A$ через $a$ . Тогда в множестве $B$ всего $N-a$ городов. Стоимость самого дешевого пути между городами одного множества, как было показано выше, не уменьшилась. Значит, лишь между $a(N-a)$ парами городов из разных множеств стоимость самого дешевого пути могла уменьшиться. Это количество пар не больше $N^{2} / 4$ , по неравенству между средними арифметическим и геометрическим.

Новый самый дешевый путь между городами из разных множеств проходит по удешевленному ребру $X Y$ не более одного раза, а до удешевления стоимость такого же пути была не ниже стоимости самого дешевого пути между этими городами. Поэтому для каждой пары городов из разных множеств стоимость самого дешевого пути уменьшилась не более, чем на 1000. Значит, итоговая сумма будет отличаться от старой не более, чем на $250 N^{2}$ рублей.