Algoritmul Ungar

[VladS]

Ar putea sa-mi dea si mie o sursa cu Algoritmul Ungar scrisa in C/C++ sau un link de pe care sa inteleg.
Stiu ca s-a dat o problema de cuplaj la runda 6 campion 2004, numai ca solutia oficiala era cu Ford-Fulkerson. Ruleaza aceasta la fel de bine ca algoritmul Ungar ?
Parca a mai fost si un referat la lot pe tema asta. Daca l-ar putea pune cineva la download i-as fi recunoscator.

[•greco]

Am sters tot, probabil ca Cosmin are dreptate.

[•Cosmin]

Mai articolele trimise la ginfo intra sub ceva drepturi de copyrigth ... si ar trebui sa astepti macar o luna dupa ce apare ginfo sa pui articolul online ca altfel ce rost are sa il mai bagam ...

[•vladcyb1]

Uite cum fac eu cuplajul maxim intr-un graf bipartit...Sursa nu este cea mai frumos scrisa dar poti sa ti faci o idee din ea. Algoritmul cupleaza nodurile folosind un greedy si apoi se bazeaza pe teorema lui Berge care zice ca atata timp cat mai exista drumuri alternante cuplajul nu este maxim. Prin drum alternant inseamna o succesiune de noduri in care unul e cuplat celalalt nu este. In momentul cand am gasit un astfel de drum inversez cuplajul si astfel el creste cu o muchie.

Cod:

type Graf=array [1..100,1..100] of integer;

var G:Graf;
    p, n, k, C, M, i, j     :integer;
    NrV, Cuplat    :array [1..100] of integer;
    marcat              :array [1..100] of boolean;
    Primul, GasitDrum    :boolean;
    act:boolean;

 procedure citire;
 var f:text;
     i,j:integer;
  begin
  assign(f,'cuplaj.in');
  reset(f);
  readln(f,n,k);
  for i:=1 to n do
   begin
   read(f,nrv[i]);
   for j:=1 to nrv[i] do read(f,g[i,j]);
   readln(f);
   end;
   close(f);
 end;

 procedure df_cuplu(x,tip:integer);
 var i,vec:integer;
  begin
  marcat[x]:=true;
  if primul then
   begin
   gasitdrum:=false;
   primul:=false;
   end
   else
   if cuplat[x]=0 { daca nu e primul si nu e cuplat inseamna ca am gasit un drum}
   then begin
        gasitdrum:=true;
        inc(m);
        end;
   i:=0;
    while (i<nrv[x])and(not gasitdrum) do
     begin
     inc(i);
     vec:=g[x,i];
     if (tip=0)and(not marcat[vec])and(cuplat[vec]<>x) then df_cuplu(vec,1);
     if (tip=1)and(not marcat[vec])and(cuplat[vec]=x) then df_cuplu(vec,0);
     if (gasitdrum)and(tip=0) then begin
                                   cuplat[x]:=vec;
                                   act:=true;
                                   cuplat[vec]:=x;
                                   end;
     end;
  end;

 procedure cupleaza_randomizat;
 var i,j:integer;
  begin
  fillchar(cuplat,2*n,0);
   m:=0;
   for i:=1 to k do
    if cuplat[i]=0 then
     for j:=1 to nrv[i] do
      if cuplat[g[i,j]]=0 then begin
                          cuplat[i]:=g[i,j];
                          cuplat[g[i,j]]:=i;
                          inc(m);
                          break;
                          end;
   end;

begin
  Citire;
  M:=0;
 cupleaza_randomizat;
  repeat
  act:=false;
  p:=1;
   while p<=n do
    begin
    if cuplat[p]=0 then begin
                  Primul:=true;
                  for i:=1 to 2*n do marcat[i]:=false;
                  df_cuplu(p,0);
                  end;
   inc(p);
   end;
  until not act;
assign(output,'cuplaj.out'); rewrite(output);
writeln(M);
close(output);
end.

[•wickedman]

Cine bagă un articol despre cuplaje sau despre alg. ungar?

[•domino]

Despre ungar a scris greco in GInfo si peste 1 luna va aparea si la noi articolul respectiv.