Национална олимпиада по информатика 2004, Задача 1.2. ПЪТИЩА
Уловието на задачата може да прочетете тук.
Решение
Условието на задачата казано използвайки математически
модел е: дадено е дърво с претеглени ребрата. Да се намери за всеки връх
разстоянието да най-отдалечения от него.
За решаването на задачата, ще използваме следната теорема:
най-отдалечения връх от някой връх на дървото е един от двата най-отдалечени в
дървото. Използвайки тази теорема задачата се свежда до това да намерим двата
най-отдалечени върха и да намерим разстоянието от тях до всеки друг. После
решението за всеки връх ще бъде по-голямото от двете разстояния. Но преди да
видим как ще реализираме това, ще докажем теоремата.
Нека двата най-отдалечени върха в дървото са A и B. Ще вземем връх C
и ще допуснем,
че най-далечния от него не е нито A или B, а връх D. Доказателството ще има два случая.
Първият, от които е когато върхът C лежи на пътя между A
и B. Да разгледаме фигура 1. Върхът E е последния общ в пътищата между A и B и между C и D. С буквите x, y, z, w ще означим дължините на пътищата
между A и C, E и B, C и E, Е и D. От твърдението, че най-отдалечения от
A е B следва, че x + w
+ y > x + w + z, което е еквивалентно на y > z. От
твърдението, че най-отдалечения връх от C e D следва, че w + z > w + y, което е еквивалентно на z > y. Така получихме две противоречиви твърдения.

Вторият случай на доказателството е когато точка C не лежи на пътя между A и B. Да разгледаме фигура 2. Върхът E е първият общ за пътищата от A до B и от C до B. С буквите x, y, z, w
ще означим дължините на пътищата между A и E, E и B, E и C, C и D. От твърдението, че
най-отдалечения от A е B следва, че x + y > x + z + w, от което следва, че y > z + w от което, че y > w. От твърдението, че най-отдалечения от
C е D следва, че w > z + y от което, че w
> y. Така пак
получихме две противоречиви твърдения породени от нашето предположение, че има
връх D, който е на по-голямо
разстоянието от C от колкото A или B. С това теоремата е доказана.
Сега остава да намерим двата най-отдалечени върха в
дървото и да намерим разстоянието от тях до всеки връх. Намирането на
разстоянията от един връх до всички други в дърво става като използваме търсене
в дълбочина или ширина. Търсенето в дълбочина предполага използване на
рекурсия, което на свой ред използването на стека на програмата, който за
рекурсия с голяма дълбочина няма да може да побере всичките извиквания на
рекурсивната функция. Затова използването на търсене в ширина е правилния
подход тук. И двата алгоритъма имат сложност O(N+M).
За да решим задачата ще пуснем търсене в ширина от
произволен връх. Най-отдалечения намерен връх е един от двата най-отдалечени.
Пускайки търсене в ширина и от него ще намерим и другия от двата
най-отдалечени. Сега по същия начин може да намерим разстоянията от двата
най-отдалечени до всички други и за всеки връх да изберем по-голямото от двете.
Трябва да се внимава за типа, в който съхраняваме резултата. 32 битова целочислена
променлива не е достатъчна.
Примерна реализация
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100001;
struct Edge
{
int v, w;
Edge(int nv, int nw)
{
v = nv;
w = nw;
}
};
struct Vex
{
vector<Edge> es;
int v;
};
int n, m;
vector<Vex> vs;
double d1[maxn], d2[maxn];
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i, a, b, c;
void setv(int v);
void bfs(int v, double d[]);
scanf("%d%d", &n, &m);
vs.resize(n + 1);
for (i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &c);
vs[a].es.push_back(Edge(b, c));
vs[b].es.push_back(Edge(a, c));
}
setv(0);
bfs(1, d1);
a = 1;
for (i = 2; i <= n; i++)
if (d1[i] > d1[a])
a = i;
setv(0);
bfs(a, d2);
b = 1;
for (i = 2; i <= n; i++)
if (d2[i] > d2[b])
b = i;
setv(0);
bfs(b, d1);
for (i = 1; i <= n; i++)
printf("%.0f\n", max(d1[i], d2[i]));
}
void bfs(int v, double d[])
{
queue<int> q;
int i, a;
d[v] = 0.0;
vs[v].v = 1;
q.push(v);
while (!q.empty())
{
v = q.front();
q.pop();
for (i = 0; i < vs[v].es.size(); i++)
{
a = vs[v].es[i].v;
if (vs[a].v == 0)
{
d[a] = d[v] + vs[v].es[i].w;
vs[a].v = 1;
q.push(a);
}
}
}
}
void setv(int v)
{
int i;
for (i = 1; i <= n; i++)
vs[i].v = v;
}
Автор: Иван Анев
обратно към брой 27
|