INFOMAN брой 10
{ This is the input data: N; S1 h1 m1; S2 h2 m2; ...; S(N) h(N) m(N).
5
28 3 40
4 4 60
10 2 30
16 2 50
1 5 20
ВИСОКА КУЛА
-----------
Дадени са N (N<=250) цилиндъра, за всеки от които са известни лицето на
основата, височината и масата. Един цилиндър може да се постави върху друг
само ако той има по-малко лице и по-малка основа от другия. Поставяйки един
върху друг цилиндрите можем да строим кули. Да се намери височината на най-
високата кула, която може да се построи от дадените цилиндри.
РЕШЕНИЕ: Да разгледаме цилиндрите като върхове на насочен граф, в който
ребра има от връх v1 към връх v2 точно когато цилиндър v2 може да се поста-
ви върху цилиндър v1. Търси се максимален път в този граф. По принцип зада-
чата за намиране на максимален път в граф е NP-пълна и не може да се реши с
полиномиален алгоритъм и от това възниква заблудата, че задачата е нерешима.
Всъщност задачата има решение (доц. Краси Манев обикновено не дава нерешими
задачи по състезанията). Понеже по-малък цилиндър не може да се постави вър-
ху по-голям, то в насочения граф не може да има цикли (контури). Това озна-
чава, че графа е безконтурен. В книгата "Комбинаторика для програмистов" на
Липски е описан класически алгоритъм за намиране на максимален път в безкон-
турен граф. Алгоритъмът първо преномерирва номерата на върховете в графа по
такъв начин, че всички наследници на върха i (не само непосредствените) да
имат по-голям номер от i, а след това прилага динамично оптимиране за нами-
ране на максималния път до всеки от върховете. Идеята на оптимирането е, че
този максимален път за върха i се получава от максималните пътищата за всич-
ки върхове предшественици на i, които са вече изчислени. Те са вече изчисле-
ни, защото изчисленията извършваме подред от връх 1 до връх N и винаги кога-
то изчисляваме максималния път завършващ във връх i, максималните пътища до
всички предшественици на i са вече изчислени. Тогава пътят F(i) до връх i е
F(i) = h ако i няма предшественици или
F(i) = Max( F(j)+h ) където j са всички върхове,
които са предшественици на i, h е височината на i
на кулата, която е означена с връх i в графа. Навсякъде под връх v се разби-
ра върха, който има номер i след преномерирването на върховете в графа.
Преномерирването на върховете става по стандартния алгоритъм за топологично
сортиране на върховете на граф: Докато може намираме връх, който няма пред-
шественици; премахваме го от графа за едно с всички инцидентни с него ребра;
съпоставяме му поредния номер. За да извършим топологичната сортировка най-
ефективно, си правим един масив, в който си пазим за всеки връх колко преки
предшественика има и когато изтриваме връх от графа, актуализираме този ма-
сив като намаляваме броя на предшествениците на всички наследници на върха.
След това изчисляваме последователно за всеки връх по дадената по-горе фор-
мула дължината на най-дългия път, завършващ в него.
Забележка: Топологичното сортиране и динамичното оптимиране могат да се нап-
равят едновременно.
}
CONST MaxN = 250;
InFileName = 'TOW.PAS';
OutFileName = '';
TYPE TCylinder = record S,h,m: integer; end;
VAR C: array[1..MaxN] of TCylinder;
N: integer;
Order: array[1..MaxN] of integer;
Procedure ReadData; { Read the input data - N, C[1..N] }
Var F: Text;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N);
for N:= 1 to N do
with C[N] do
Read(F, S,h,m);
Close(F);
End;
Function CanBePut(Up,Down:integer): boolean;
Begin { Return if the cylinder Up can be put over cylinder Down }
CanBePut:= (C[Down].S > C[Up].S) and (C[Down].m > C[Up].m);
End;
Procedure TopSort; { Sort topologicaly the graph. The result is Order[1..N] }
Var ParentsCount: array[1..MaxN] of integer;
Used: array[1..MaxN] of boolean;
I, J, Count: integer;
Begin
{ finding the number of parents for each vertice - ParentsCount[1..N] }
FillChar(ParentsCount,SizeOf(ParentsCount),0);
for I:= 1 to N do
for J:= 1 to N do
if CanBePut(J,I) then {J can be on I}
Inc(ParentsCount[J]);
{ apply a topological sorting of the graph to obtain Order[1..N] }
FillChar(Used,SizeOf(Used),false);
for Count:= 1 to N do
for I:= 1 to N do
if not Used[I] then
if ParentsCount[I] = 0 then
begin { when a vertice without father is found }
Order[Count]:=I;
Used[I]:=true; {remove the vertice I with all its edges}
for J:= 1 to N do
if CanBePut(J,I) then
Dec(ParentsCount[J]);
Break;
end;
End;
Procedure FindMaxCylindersHeight;
Var MaxHeight: array[1..MaxN] of integer;
Cur, Prev, Max: integer;
OutF: Text;
Begin
{ Calculating the maximal height - MaxHeight[V] finishing in vertice V }
for Cur:= 1 to N do
begin
Max:=C[Order[Cur]].h;
for Prev:= Cur-1 downto 1 do
if CanBePut(Order[Cur],Order[Prev]) then
if MaxHeight[Prev] + C[Order[Cur]].h > Max then
Max:= MaxHeight[Prev] + C[Order[Cur]].h;
MaxHeight[Cur]:=Max;
end;
{ Find and print the height of heightest tower }
Max:=0;
for Cur:= 1 to N do
if MaxHeight[Cur] > Max then Max:=MaxHeight[Cur];
Assign(OutF,OutFileName); Rewrite(OutF);
WriteLn(OutF,Max);
Close(OutF);
End;
BEGIN
ReadData;
TopSort;
FindMaxCylindersHeight;
END.