Текущ брой на Списание ИнфоМан
 


Зимни Математически Състезания 2005, Задача B2. ГЕЙМЪРСКИ ПЪТИЩА

Условието на задачата може да прочетете тук.

Решение

Прочитайки задълбочено условието на задачата виждаме, че "картата" на Панчо всъщност едърво, чиито върхове са кръстовищата, а ребрата между тях са улиците, свързващи тезикръстовища. Върховете са два вида - такива с гейм зали и обикновени кръстовища.Новото условие на задачата е: да се намери на всеки връх най-близкия връх от първиявид (тези с гейм зали) и разстоянието до този връх.

Нека разгледаме произволeн връх k. Най-близката гейм зала до този връх е или k (акоk e гейм зала), или най-близката гейм зала до някой от неговите наследници, или най-близката гейм зала до неговия баща (предшественик). Тъй като ще правим извода за решението на k спрямо два вида върхове: предшествениции наследници, ще ни се наложи и два пъти да обхождаме този връх (един път когатотърсим решението му спрямо наследниците му и веднъж, когато търсим решението спрямопредшественика му).

Задачата може да се реши или с 2 DFS (обхождане в дълбочина) или с 2 BFS (в ширина).За да избегнем евентуални проблеми със Stackoverflow е препоръчително да изберем BFS.

Нека разгледаме първото обхождане - от листата нагоре към корена на дървото,т.е.решаваме задачата за всеки връх k спрямо неговите наследници. Забележете, че преди дазапочнем да обхождаме вече сме намерили най-близките гейм зали за върховете,които имат гейм зали - самите тях. В условието обаче ясно е споменатода се търсят различни върхове, затова се налага да намерим не само най-доброто решение,а и второто най-добро. По този начин сме сигурни, че едно от двете решения (ипо-точно второто най-добро) ще съдържа връх с различен индекс от себе си.Връщайки се към обхождането, оттук нататък следва стандартната част. Проверяваме за бащатата на разглеждания връх (да го наречем k) дали решениетоза k + реброто от k до баща му е по-добро от текущо намереното за баща му. Ако не е,сравняваме най-доброто за k с второто най-добро за баща му. Отделно също трябва дасравним и двете втори най-добри решения (тъй като може да имаме случай в който трябвада "препишем" първото и второто най-добро решение за k в решенията за баща му).

Вече сме обходили всички върхове (в ред - от листата на дървото към корена). По тозиначин можем да твърдим, че със сигурност сме намерили истинското решение за корена надървото. Това е така, защотото коренът е единственият връх в дървото без предшественик, а вече сме намерили решенията спрямо неговите наследници, следователно сме намерили истинското решение. За всички останали върхове трябва да разглеждаме и другия случай – да търсим решението спрямо техните родители. Това става отново с BFS, този път обаче в опашката на BFS отначало стои коренът на дървото, а не листата. Правим аналогични проверки както в случая на първото BFS и така вълнообразно намираме решенията за корените на различните поддървета, които излизат от текущия връх (първоначално - корена на цялото дърво). После добавяме вече "сигурните" върхове в опашката на BFS и така докато не обходим всички върхове.

Относно реализацията - има два удобни начина да представим дървото. Единият е със списъци на съседство за всеки връх, а другият е чрез един списък от ребра, като всяко ребро го добавяме два пъти - ако реброто е (a, b), добавяме реброто веднъж като (a, b) и веднъж като (b, a). За всяко ребро пазим и още една стойност - индекса на следващото ребро, на което първия връх е съответно a или b. В друг масив си пазим за всеки връх индекса на началото на този списък от инцидентни на него ребра. Идеята е много подобна с тази на списъците на съседство. Реализацията обаче е далеч по-лесна и елегантна.

Сложността на DFS и BFS, когато графът G(E, V) е представен със списъци, е O(E+V) - брой върхове + брой ребра.

Примерна реализация:

program gpaths;

const
	MAXN = 100000;
    INF  = maxlongint;

type
	Integer = LongInt;
	TEdge   = record
		a, b, c, n   : Integer;
	end;

var
	G                      : Array [1 .. 2 * MAXN] of TEdge;
	s1, s2                 : Array [1 .. MAXN] of Int64;
	s1i, s2i, parent, gc   : Array [1 .. MAXN] of Integer;
	isgc                   : Array [1 .. MAXN] of Boolean;
	H, neigh               : Array [1 .. MAXN] of Integer;
	Q                      : Array [1 .. MAXN] of Integer;
	qb, qe                 : Integer;
	N, K, N2               : Integer;

procedure Init;
var
	i   : Integer;
begin
	for i := 1 to MAXN do begin
		neigh[i] := 0;
		H[i] := 0;
		isgc[i] := False;
	end;
end;

procedure readInput;
var
	i, a, b, c   : Integer;
begin
	N2 := 0;
        readln(N, K);
	for i := 1 to (N-1) do begin
                readln(a, b, c);
		neigh[a] := neigh[a] + 1;
		neigh[b] := neigh[b] + 1;
		N2 := N2 + 1;
		if (H[a] = 0) then begin
			H[a] := N2;
			G[N2].n := 0;
		end else begin
			G[N2].n := H[a];
			H[a] := N2;
		end;
		G[N2].a := a; G[N2].b := b; G[N2].c := c;
		N2 := N2 + 1;
		if (H[b] = 0) then begin
			G[N2].n := 0;
			H[b] := N2;
		end else begin
			G[N2].n := H[b];
			H[b] := N2;
		end;
		G[N2].a := b; G[N2].b := a; G[N2].c := c;
	end;
	for i := 1 to K do begin
                readln(f, a);
		isgc[a] := True;
		gc[a] := i;
	end;
end;

procedure writeOutput;
var
	i   : Integer;
begin
	for i := 1 to N do
		if (s1i[i] = i) then
			writeln(gc[s2i[i]], ' ', s2[i])
		else
			writeln(gc[s1i[i]], ' ', s1[i]);
end;

procedure Solve;
var
	c, i, c2   : Integer;
begin
	for i := 1 to N do begin
		s2[i] := INF;
		if (isgc[i]) then begin
			s1[i] := 0;
			s1i[i] := i;
		end else
			s1[i] := INF;
	end;
	qb := MAXN + 1;
	qe := MAXN;
	for i := 1 to N do
		if (neigh[i] = 1) then begin
			qb := qb - 1;
			q[qb] := i;
		end;
        while (qb <= qe) do begin
		c := q[qe];
		qe := qe - 1;
		neigh[c] := 0;
		i := H[c];
		while (i > 0) do begin
			c2 := G[i].b;
			if (neigh[c2] = 0) then begin
				i := G[i].n;
				continue;
                        end;

			if (s1[c] + G[i].c < s1[c2]) or
			((s1[c] + G[i].c = s1[c2]) and 
			(s1i[c] < s1i[c2])) then begin
				s2[c2] := s1[c2];
				s2i[c2] := s1i[c2];
				s1[c2] := s1[c] + G[i].c;
				s1i[c2] := s1i[c];
			end else if (s1i[c] <> s1i[c2]) 
				and ((s1[c] + G[i].c < s2[c2]) or
				((s1[c] + G[i].c = s2[c2]) and 
				(s1i[c] < s2i[c2]))) then begin
				s2[c2] := s1[c] + G[i].c;
				s2i[c2] := s1i[c];
			end;
			if (s2[c] + G[i].c < s2[c2]) or
			((s2[c] + G[i].c = s2[c2]) and 
			(s2i[c] < s2i[c2])) then begin
				s2[c2] := s2[c] + G[i].c;
				s2i[c2] := s2i[c];
			end;

			neigh[c2] := neigh[c2] - 1;
			if (neigh[c2] = 1) then begin
				qb := qb - 1;
				q[qb] := c2;
			end;
			i := G[i].n;
		end;
	end;

	parent[c] := 0;
	qb := MAXN;
	qe := MAXN;
	q[qb] := c;

	while (qb <= qe) do begin
		c := q[qe];
		qe := qe - 1;
		i := H[c];
		while (i > 0) do begin
			c2 := G[i].b;
			if (parent[c] = c2) then begin
                        	i := G[i].n;
			 	continue;
                        end;

			if (s1[c] + G[i].c < s1[c2]) or
			((s1[c] + G[i].c = s1[c2]) and 
			(s1i[c] < s1i[c2])) then begin
				s2[c2] := s1[c2];
				s2i[c2] := s1i[c2];
				s1[c2] := s1[c] + G[i].c;
				s1i[c2] := s1i[c];
			end else if (s1i[c] <> s1i[c2]) and 
			((s1[c] + G[i].c < s2[c2]) or
			((s1[c] + G[i].c = s2[c2]) and 
			(s1i[c] < s2i[c2]))) then begin
				s2[c2] := s1[c] + G[i].c;
				s2i[c2] := s1i[c];
			end;
			if (s2[c] + G[i].c < s2[c2]) or
			((s2[c] + G[i].c = s2[c2]) and 
			(s2i[c] < s2i[c2])) then begin
				s2[c2] := s2[c] + G[i].c;
				s2i[c2] := s2i[c];
			end;			
			
			parent[c2] := c;

                	qb := qb - 1;
                        q[qb] := c2;

			i := G[i].n;
		end;
	end;

end;

begin
	Init;
	readInput;
	Solve;
	writeOutput;
end.

Автор: Момчил Иванов


обратно към брой 27