Найдите остовное дерево с максимальной общей мощностью затопления.Наименьшая пропускная способность ребра в этом дереве - это пороговое значение, при котором сеть станет отключенной.
Дерево «максимальной емкости» совпадает с остовным деревом с минимальным весом с весами ребер, равными отрицательной емкости, поэтому вы можетенайдите это дерево, используя алгоритм Крускала или Прима.
Алгоритм Крускала, очевидно, выполняет именно то, что вы хотите - обрабатывает ребра в порядке убывания емкости, пока сеть не подключится: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
УдивительноДело в том, что если вы не знакомы со структурой данных о непересекающихся множествах, это то, что она очень быстрая.
Любой алгоритм поиска минимального остовного дерева тоже сделает то же самое, но это небольшая работа, чтобы доказатьчто.