Национална олимпиада по информатика 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