Автор разбора Кускова Юлия (9 класс, Гимназия 1 г.Витебск)
В одном государстве имеется NN городов. Некоторые города соединены дорогами, причем для любых двух городов AA и BB выполняется следующее свойство: существует ровно один способ попасть из города AA в город BB если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.
Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов AA, BB и CC минимальное количество дорог, которое необходимо использовать, чтобы доехать от AA до BB, затем от BB до CC и затем от CC до AA (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).
Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.
Входные данные
В первой строке вводится число NN - количество городов (3 <= NN <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит KiKi - количество городов, с которыми он соединен дорогами (1 <= KiKi < NN), а затем KiKi чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.
Выходные данные
Выведите три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них.
Пример
входные данные
5
1 3
1 3
3 1 2 4
2 3 5
1 4
выходные данные
5 2 1
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define pb push_back #define F first #define S second #define usl unsigned long long #define ll long long #define ull unsigned long long #define pll pair <int, int> using namespace std; const int INF = int (1e9); vector <int> g[1002]; int dfs (int v, int pred, int &vm) { //v - текущая вершина, pred - предок, vm - вершина, которую мы считаем наиболее удаленной int len = 1, vd; vm = v; for (auto to : g[v]) if (to != pred) { int pr = dfs (to, v, vd) + 1; //промежуточное значение if (pr > len) { len = pr; vm = vd; } } return len; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif // LOCAL int n; cin >> n; for (int i = 0; i < n; ++i) { int m; cin >> m; for (int j = 0; j < m; ++j) { int a; cin >> a; --a; g[i].push_back (a); } } int len = 0, v1, v2, v3; //суммарное расстояние между вершинами, вершины - ответ на задачу for (int i = 0; i < n; ++i) { if (g[i].size() == 1) //подвешивать дерево за листья не выгодно continue; pair <int, int> r [g[i].size()]; //первый элемент в паре - расстояние до наиболее удаленной вершины в поддереве, второй - ее номер for (int j = 0; j < g[i].size(); ++j) r[j].first = dfs (g[i][j], i, r[j].second); sort (r, r + g[i].size(), greater <pair <int, int>>()); //сортировка по невозрастанию if (g[i].size() == 2) { if (len < r[0].first + r[1].first) { len = r[0].first + r[1].first; v1 = r[0].second; v2 = r[1].second; v3 = i; } } else if (len < r[0].first + r[1].first + r[2].first) { len = r[0].first + r[1].first + r[2].first; v1 = r[0].second; v2 = r[1].second; v3 = r[2].second; } } cout << v1 + 1 << ' ' << v2 + 1 << ' ' << v3 + 1; //ответ выводится в 1-индексации return 0; }