INFOMAN брой 2
{ This is the input data: N M; Mnoj_1; Mnoj_2; ...; Mnoj_M;
5 5
1 2 3 4
1 3
1 4 3
1 2 3 4
2 3 5
ПРЕДСТАВИТЕЛИ НА МНОЖЕСТВО
--------------------------
Дадени са M множества от числа, като всяко число е в интервала от 1 до N.
Да се избере от всяко множество точно по 1 число /представител/, така че
избраните числа да са различни по между си.Ако задачата няма решение (не
може да се избере представител от всяко множество),да се изберат предста-
вители на максимален брой от множествата. В изходния файл да се отпечата
на всеки ред i=1,2,..,M представителя на i-тото множество или 'няма' ако
няма представител.
РЕШЕНИЕ:
Нека съставим неориентиран граф от входните данни по следния начин:
Графът да се състои от M+N върха. Върховете от 1 до N да съответстват на
елементите от 1 до N, а върховете от N+1 до N+M да съответстват на множе-
ствата от 1 до M. Неориентирано ребро (v1,v2) между два върха да се пос-
тавя точно тогава,когато на върха v1 съответства на елемент /v1=1..N/, а
на другия връх v2 съответства множество /v2=N+1..M/ и множеството, което
съответства на v2 съдържа елемента v1. С други думи от всеки елемент има
ребро до всяко множество,в което той се съдържа. От тук нататък за да ре-
шим задачата, е достатъчно да намерим максималното двойкосъчетание в със-
тавения така граф и той е всъщност решението на задачата. Ребрата, които
съставят масксим.двойкосъчетание свързват всяко множество с неговия пред-
ставител.
Двойкосъчетание в неориентиран граф наричаме такова подмножество на ребра-
та на графа, че в това множество да няма две ребра, които са инцидентни на
един и същ връх от графа.Такова двойкосъчетание с максимален брой ребра се
нарича максимално двойкосъчетание в граф. За намиране на максималното двой-
косъчетание в граф ще използваме следния алгоритъм:
Основната идея е докато може, да се намира "редуващ увеличаващ път" и да се
инвертират ребрата на текущото двойкосъчетание с този път. Има теорема, ко-
ято твърди, че ако в един граф няма редуващ увеличаващ път, то двойкосъчета-
нието в този граф е максимално. "Редуващ увеличаващ път" се нарича път, кой-
то започва от свободен връх, продължава със свободно ребро,с двойкосъчетава-
що ребро, отново със свободно ребро, .... и завършва със свободен връх. Два
свободни върха, съединени със свободно ребро също са увел. път. При наличие-
то на такъв път,текущото двойкосъчетание се увеличава с 1 ребро, като се ин-
вертират ребрата, съдържащи се в този път: двойкосъчетаващите стават свобод-
ни, а свободните,които са с 1 повече, стават двойкосъчетаващи. Търсенето на
такъв увелич. път се извършва чрез търсене в дълбочина, като всеки връх се
посещава най-много два пъти: веднъж от свободен връх и веднъж от двойкосъче-
тан връх. Това води до линейна сложност на търсенето - 2N. Общата сложност
на алгоритъма е по-голяма от N*N, но винаги по-малка N*N*N и зависи от зада-
дения граф.
Реализацията на алгоритъма е до N=M=1000, но при условие, че графа има под
250000 ребра. Иначе не достига паметта. За пълен граф работи до N=M=250.Гра-
фът се представя чрез масив за върховете и динамично разположен масив съдър-
жащ инцидентните върхове на всеки връх. За масива (списъка на инциденстност)
за всеки се заделя толкова динамична памет, колкото инцидентни върха има съ-
ответния връх. Така се представят графи с голям брой върхове и ребра.
}
{$M 32768,0,655360}
{$R-,S-,Q-}
CONST InFileName = 'P3.PAS';
OutFilename = '';
MaxN = 1000;
TYPE SasediList = array[1..MaxN] of word; {Списък на инцидентните върхове}
PSasediList = ^SasediList;
Vruh = record
Pair: word; {Върхът, с който е двойкосъчетан текущия или 0}
InStack, {Дали е използван при търсенето на увел.път}
PosetenFromFree, {Дали е посетен от свободно ребро}
PosetenFromPair: boolean; {Дали е посетен от двойкосъч.ребро}
BrSasedi: word; {Брой инцидентни върхове}
Sasedi: PSasediList; {Списък на инцидентните върхове}
end;
VAR G: array[1..2*MaxN] of Vruh;
N,M: word;
FoundReduvUvelPath: boolean;
Stek: array[1..2*MaxN] of
record v1,v2:word end;
SP: integer;
Procedure ReadData; {Прочита входните данни от същия файл}
Procedure AddRebro(u,v:integer);
Var S: PSasediList;
Begin
with G[u] do
begin
GetMem( S, (BrSasedi+1)*SizeOf(word) );
Move( Sasedi^, S^, BrSasedi*SizeOf(word) );
FreeMem( Sasedi, BrSasedi*SizeOf(word) );
Inc(BrSasedi); S^[BrSasedi]:=v;
Sasedi:= S;
end;
End;
Var I,J: word;
F: Text;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
FillChar(G,SizeOf(G),0);
ReadLn(F,N,M);
for I:= N+1 to N+M do
begin
while not seekeoln(f) do
begin Read(F,J); AddRebro(I,J); AddRebro(J,I); end;
ReadLn(F);
end;
Close(F);
N:=N+M;
End;
Procedure Podobri; {Подобрява двойкосъчетанието с 1 двойка според намерения}
Begin {увеличаващ редуващ път. Инвертира двойкосъчетаните ребра от стека}
FoundReduvUvelPath:=true;
for SP:= 1 to SP do
with Stek[SP] do
begin G[V1].Pair:=V2; G[V2].Pair:=V1; end;
End;
Procedure FindFreeRebro(V:word); forward;
Procedure FindPairRebro(V:word); {Търси в дълбочина увеличаващ път като}
Begin {взема за следващо ребро двойкосъчетаващото ребро на текущия връх V}
with G[V] do
begin
if FoundReduvUvelPath or PosetenFromFree or InStack then Exit;
PosetenFromFree:=true;
InStack:=true; Stek[SP].V2:=v;
if Pair = 0 then
Podobri {Текущия върх е свободен --> намерен е увеличаващ път}
else
FindFreeRebro(Pair); {Продължаваме с върха, който е двойкосъч. с V}
InStack:=false;
end;
End;
Procedure FindFreeRebro(V:word); {Търси в дълбочина следващо ребро за}
Var I: word; {увеличаващ път,като търсенето започва от свободно ребро}
Begin
with G[V] do
begin
if FoundReduvUvelPath or PosetenFromPair or InStack then Exit;
PosetenFromPair:=true;
InStack:=true; Inc(SP); Stek[SP].V1:=v;
for I:= 1 to BrSasedi do
if Sasedi^[I] <> Pair then {Ако реброто е свободно, минаваме по него}
FindPairRebro(Sasedi^[I]);
Dec(SP); InStack:=false;
end;
End;
Procedure FindMaximalDvoikosachetanie;
Var BegVr,I: integer;
Begin
repeat
FoundReduvUvelPath:=false;
for BegVr:= 1 to N do
if G[BegVr].Pair = 0 then
begin {Ако върхът е свободен, търсим увел. път от него}
for I:= 1 to N do
with G[I] do
begin PosetenFromFree:=false; PosetenFromPair:=false; end;
G[BegVr].PosetenFromFree:=true;
SP:=0; FindFreeRebro(BegVr);
if FoundReduvUvelPath then Break;
end;
until not FoundReduvUvelPath; {Докато не се случи да няма увелич. път}
End;
Procedure PrintSolution;
Var F: Text;
I: word;
Begin
Assign(F,OutFileName); Rewrite(F);
for I:= N-M+1 to N do
with G[I] do
if Pair = 0 then
WriteLn('няма')
else WriteLn(F,Pair);
WriteLn(F);
Close(F);
End;
BEGIN
ReadData;
FindMaximalDvoikosachetanie;
PrintSolution;
END.