|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 04-4. Издевательство
(Разбор)
Нам требуется найти цикл длины 3 минимального веса в полном взвешенном графе. Переберем всевозможные тройки вершин (это можно сделать, например, тремя вложенными циклами - каждая из переменных цикла соответствует какой-то из трех искомых вершин). Любая тройка однозначно задает цикл длины три. Выберем тройку, для которой вес соответсвующего цикла минимален.