В графе G с каждым ar c емкость равна 1, а кратчайшая длина от s до t равна k, минимальная емкость st - O (n ^ 2 / k ^ 2), где n - количество вершин , n выбор 2 дает O (n ^ 2) количество дуг, я не уверен, как аргументировать дальше, чтобы оправдать утверждение. Если я думаю, что каждый из st-путей имеет длину k, это дает мне O (n ^ 2 / k) возможных пересечений. Может быть, я не совсем правильно думаю. Любой вид ввода будет высоко ценится