Бинпоиск и кратчайшие пути

Есть формулировка, на которую надо реагировать рефлекторно: максимизировать минимум или минимизировать максимум. Почти всегда это бинпоиск по ответу, а внутри проверки — что-нибудь простое.

В графовых задачах внутри проверки почти всегда стоит обход.

Задача про грабителей

Невзвешенный граф. Караван едет из $S$ в $F$ по какому-то из кратчайших путей — по какому именно, неизвестно. В вершине $R$ сидят грабители; увидев маршрут, они нападут в той его вершине, которая ближе всего к $R$.

Вопрос: какой самый плохой для грабителей случай? То есть чему равен

$$\max_{\text{кратчайшие пути } P}\ \min_{v \in P} \operatorname{dist}(R, v)$$

Максимум минимума — значит, бинпоиск.

Что проверять

Проверяем: верно ли, что на каждом кратчайшем пути есть вершина на расстоянии не больше $x$ от $R$?

Свойство монотонно. При $x = -1$ шар пуст, ни один путь не задет. При $x = n$ в шар попадают все вершины, задеты все пути. Между ними — одна точка переключения, и это ответ.

Проверка выглядит так:

1. Обходом от $R$ посчитать dr — расстояния до всех вершин.
2. Запретить все вершины с dr[v] <= x.
3. Запустить обход от $S$ по незапрещённым вершинам.
4. Если расстояние до $F$ не изменилось, остался нетронутый кратчайший путь: $x$ мал.

Ключевой момент в четвёртом пункте. Сравнивать надо не «дошли или нет», а «сохранилась ли исходная длина». Путь может остаться, но стать длиннее — а нас интересуют только кратчайшие.

vector<int> bfs(int s, const vector<char>& ban) {
    vector<int> d(n, -1);
    if (ban[s]) return d;
    queue<int> q; d[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : g[v])
            if (!ban[u] && d[u] == -1) { d[u] = d[v] + 1; q.push(u); }
    }
    return d;
}

int solve(int S, int F, int R) {
    vector<char> none(n, 0);
    auto base = bfs(S, none);
    auto dr = bfs(R, none);
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        vector<char> ban(n, 0);
        for (int v = 0; v < n; v++)
            if (dr[v] != -1 && dr[v] <= mid) ban[v] = 1;
        auto d = bfs(S, ban);
        bool escaped = (d[F] != -1 && d[F] == base[F]);
        if (escaped) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Два обхода на подготовку, по одному на итерацию бинпоиска: $O((n + m)\log n)$.

Проверено: на 18 356 случайных графах результат совпал с прямым перебором всех кратчайших путей.

Почему это стоит замечать

Без бинпоиска задача выглядит тяжёлой: кратчайших путей может быть экспоненциально много, перебрать их нельзя.

С бинпоиском она разваливается на два обхода и цикл. Причём проверяемое условие получилось проще исходного вопроса — это типично: бинпоиск меняет «найдите оптимум» на «проверьте порог», и второе почти всегда легче.

Задач, где минимизируется максимум или максимизируется минимум, в олимпиадном программировании много — оценка «каждая двадцатая» звучит правдоподобно. Привычка проверять эту формулировку окупается: она бесплатно упрощает задачу ещё до того, как вы начали думать.

Ещё две постановки той же формы

Грузоподъёмность. Максимизировать число кружек в машине при ограничении на время в пути. Чем больше груз, тем меньше дорог доступно. Проверка: выбросить слишком слабые рёбра, запустить Дейкстру, сравнить с лимитом времени. Разбор — в статье про неявный граф.

Минимизировать максимальное ребро на пути. Проверка: оставить рёбра веса не больше $x$ и спросить достижимость обычным обходом. Отдельно отметим, что здесь бинпоиск не обязателен — то же самое даёт минимальное остовное дерево, — но написать бинпоиск обычно быстрее.

Общий признак: ответ — число, монотонность по нему очевидна, а проверка сводится к запуску того, что вы и так умеете писать.