Не уверен насчет алгоритма в графе

Question

У меня есть этот вопрос:

Учитывая ориентированный и связный граф G = (V, E) с положительными весами, определяем E (t) как группу ребер, вес которых не больше t. Найдите алгоритм, который вычисляет минимальное t, которое для него G (t) = (V, E (t)) является связностью.

Я думал о том, чтобы найти минимальный срез максимального потока графика, но я не уверен, что это правильное направление к решению.

Answer 1

Сначала отметим, что если p Давайте определим функцию boolean isConnected(int k), которая проверяет, подключен ли G (k) (вы можете реализовать это самостоятельно). (*) подразумевает, что функция isConnected возвращает false для k = answer.

Это означает, что вы можете использовать алгоритм двоичного поиска, чтобы найти ответ.