1
Автор разбора Кускова Юлия (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;
}
