В государстве 28 городов располагаются на территории областей так, что любые два города из одной области соединены дорогой и никакие два города из разных областей дорогой не соединены. Оказалось, что ответственность за состояние дорог можно распределить между двумя областными министерствами следующим образом: не найдётся таких трёх городов A, B, C из одной области, чтобы дороги AB, BC и CA обслуживались бы одним министерством. Какое наибольшее число дорог может быть в этом государстве?
Пусть в государстве имеется несколько областей, каждая из которых содержит некоторое число городов. Из условия известно, что внутри каждой области между любыми двумя городами проведена дорога (то есть область соответствует полному графу), а между городами разных областей дорог нет. Кроме того, дороги раскрашены (то есть обслуживаются одним из двух министерств) так, что не существует трёх городов A, B, C из одной области, для которых все три дороги AB, BC, CA принадлежат одному и тому же министерству.
Важно то, что если в области n городов, то её дороги представляют полный граф...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Не нашел нужную задачу?