Дан неориентированный взвешенный связный граф из n вершин и m ребер. Никита и Миша играют в игру. Сначала Никита красит каждую вершину графа в один из двух цветов (в том числе разрешается покрасить все вершины в один цвет). После этого Миша выбирает две различные вершины s и t, покрашенные Никитой в одинаковый цвет. Результатом игры считается расстояние между вершинами s и t в графе (минимальная сумма весов ребер на пути между s и t). Никита стремится максимизировать итоговый результат, а Миша — минимизировать. Найдите итоговый результат игры, если Никита и Миша играют оптимально. Формат входных данных Первая строка содержит два целых числа n и m(3≤n≤200000, n−1≤m≤min(n*(n−1)/2,200000)) — количество вершин и ребер графа соответственно. Следующие m строк содержат три целых числа u, v и w (1≤u

Рассмотрим задачу и разберёмся, как найти оптимальный результат в игре Никиты и Миши.

Анализ задачи:

• Имеется связный неориентированный граф с n вершинами и m рёбрами.
• Никита красит вершины в два цвета (может все в один).
• Миша выбирает две вершины s и t, покрашенные в один цвет, и мы ищем минимальное расстояние между ними.
• Никита старается выбрать раскраску так, чтобы итоговое расстояние было максимально возможным.
• Миша выбирает минимальное такое расстояние.

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

Ключевой момент:

Чтобы Никита максимально усложнить Мише задачу, он должен "раскрасить" вершины так, чтобы минимальный путь между парой одинаковых цветов был как можно больше.

Обоснование:

• Миша выбирает пару вершин одного цвета, минимальное расстояние между которыми — d.
• Никита хочет максимизировать это d.
• Миша минимизирует d.

Ниже представлен подход:

Идея решения:

1. Рассматривать все расстояния между вершинами и находить минимальное расстояние между всеми парами, которые можно связать через определенные "уровни".
2. Использовать двухфазную стратегию:
   • Найти максимальное расстояние между двумя вершинами, чтобы выделить "отдалённые" вершины. Это делается путём поиска диаметра графа.
   • Пусть диаметр — это длина максимального пути в графе.

Почему это подходит?

Если Никита раскрасит вершины так, чтобы "крайние" вершины (например, те, что образуют диаметр графа) иметь одинаковый цвет, то минимальное расстояние между двумя вершинами одного цвета может быть равно длине этого диаметра, потому что эти вершины — самые дальние.

Алгоритм:

1. Для нахождения диаметра графа:
   • Сделать произвольный запуск поиска в ширину (BFS) из любой вершины u, чтобы найти вершину v, которая максимально удалена от u.
   • Затем выполнить BFS из v, чтобы найти расстояние до самой удалённой вершины — это длина диаметра.
2. Результат — это это диаметра графа, так как оптимальная стратегия Никиты — раскрасить вершины так, чтобы "отдалённые" вершины были одного цвета.

Итог:

Ответ — длина диаметра графа.

Реализация на C++:

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int v;
    long long w;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> g(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    // Функция для поиска самой дальней вершины из стартовой
    auto bfs = [&](int start) {
        vector<long long> dist(n + 1, LLONG_MAX);
        dist[start] = 0;
        queue<int> q;
        q.push(start);
        int farthestNode = start;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &edge : g[u]) {
                int v = edge.v;
                long long w = edge.w;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    q.push(v);
                    if (dist[v] > dist[farthestNode]) {
                        farthestNode = v;
                    }
                }
            }
        }
        return make_pair(farthestNode, dist);
    };

    // Первый запуск: произвольно выбираем вершину 1
    auto res1 = bfs(1);
    // Вторая точка, максимально удаленная от 1
    int u = res1.first;

    // Запуск из u для нахождения диаметра
    auto res2 = bfs(u);
    long long diameter = 0;
    for (int i = 1; i <= n; i++) {
        diameter = max(diameter, res2.second[i]);
    }

    cout << diameter << "\n";

    return 0;
}

Объяснение:

• Мы ищем диаметр графа, делая два прохода BFS, что эффективно за O(N + M).
• Итог — это длина максимального пути в графе, то есть результат игры при оптимальных действиях обоих игроков.

Если вам нужно более подробное объяснение или есть вопросы — пишите!