ZADATAK 2 - RAZRED - 60 bodova

TEST PODACI (skraćeni prikaz)


	Broj N	Rješenje	Broj bodova	
Test 1	2	1		4
Test 2	4	2		5
Test 3	10	8		6
Test 4	15	10		6
Test 5	20	15		8
Test 6	30	24		9
Test 7	40	34		10
Test 8	50	47		12

OPIS ALGORITMA

Nakon učitavanja podataka naš algoritam pokušava spariti što je više moguće dječaka i djevojčica u slučajevima kada su liste simpatija pojedinih dječaka i djevojčica takve da se sa sigurnošću neki od njih mogu spariti. To je moguće kada je npr. nekom dječaku simpatična samo jedna djevojčica ili nekoj djevojčici simpatičan samo jedan dječak ili npr. ako je nekom dječaku simpatično nekoliko djevojčica ali su sve te djevojčice osim jedne već sparene u ranijim pokušajima i obratno. Uglavnom, u svakom pokušaju tog početnog sparivanja izračunati ćemo za svakog dječaka i djevojčicu koliko on ima simpatija koje još nisu sparene i onda svaku takvu osobu kod koje je taj broj jednak jedan možemo spariti s njenom slobodnom simpatijom.
Nakon toga, zamišljamo naše dječake i djevojčice kao vrhove u grafu, a njihove simpatije kao bridove.
Tako smo dobili jedan bipartitan graf u kojem su neki parovi vrhova već spareni. Naš cilj je pronaći takozvane uvećane putove koji nas onda vode k povećanju broja sparenih dječaka i djevojčica.
Definirajmo :
Alternirajući put u nekom grafu je put čiji bridovi su naizmjence spareni i nespareni bridovi.
Uvećani put je alternirajući put kod kojeg su početni i krajnji vrh nespareni.
Kada pronađemo neki uvećani put on će biti oblika simpatija, veza, simpatija, veza, ..., veza, simpatija i onda ćemo jednostavno sve veze u tom uvećanom putu raskinuti, a sve simpatije proglasiti vezama i na taj način povećati broj veza za jedan.
Tražiti uvećani put možemo na dva načina, tako da graf pretražujemo metodom DFS (depth first search, u dubinu) ili BFS (breadth first search, u širinu).
Ako radimo na jednostavniji način, DFS metodom (RAZRED1.C), može nam se desiti da u grafovima s jako puno bridova naš algoritam postane prespor. Zato ćemo koristiti BFS metodu (RAZRED2.PAS, RAZRED2.C) koja je malo kompliciranija, kojom krenemo od neke nesparene djevojke i onda gradimo stablo u kojem će svi putevi iz korijena biti alternirajući.
Kada za neki od tih alternirajućih puteva otkrijemo da je i uvećani, onda napravimo uvećanje broja parova za jedan na gore opisani način.
Kod implementacije BFS metode potreban nam je i queue, a njega smo implementirali jednostavnim funkcijama init_queue, enqueue, dequeue i queue_empty.


RAZRED1.C

#include <stdio.h>

#define MAX_ZENA 50

int broj_djevojaka,max_parova = 0;
int matrica[MAX_ZENA][MAX_ZENA];
int djevojka[MAX_ZENA],momak[MAX_ZENA];
int zenske_simpatije[MAX_ZENA],muske_simpatije[MAX_ZENA];
int funkcija[MAX_ZENA];

void ucitaj (void)
{
  int i,j;
  int broj;
  FILE *fp;

  for (i = 0;i < broj_djevojaka;++i)
    for (j = 0;j < broj_djevojaka;++j)
      matrica[i][j] = 0;

  fp = fopen("RAZRED.DAT","rt");

  fscanf(fp,"%d\n",&broj_djevojaka);

  for (i = 0;i < broj_djevojaka;++i)
    do
    {
      fscanf(fp,"%d",&broj);
      if (!broj)
        break;
      matrica[i][broj - 1] = 1;
    } while (1);

  fclose(fp);
}

void rekurzija (int trenutna_djevojka,int broj_parova)
{
  int i;

  if (trenutna_djevojka == broj_djevojaka)
  {
    if (broj_parova > max_parova)
      max_parova = broj_parova;
    return;
  }

  if (broj_djevojaka - trenutna_djevojka + broj_parova < max_parova)
    return;

  for (i = 0;i < broj_djevojaka;++i)
    if (matrica[funkcija[trenutna_djevojka]][i] && !momak[i])
    {
      momak[i] = 1;
      rekurzija(trenutna_djevojka + 1,broj_parova + 1);
      momak[i] = 0;
    }

  rekurzija(trenutna_djevojka + 1,broj_parova);
}

int main (void)
{
  int i,j;
  int nasao;
  int brojac,pocetak;

  ucitaj();

  for (i = 0;i < broj_djevojaka;++i)
    momak[i] = djevojka[i] = 0;

  do
  {
    for (i = 0;i < broj_djevojaka;++i)
      zenske_simpatije[i] = muske_simpatije[i] = 0;

    for (i = 0;i < broj_djevojaka;++i)
      for (j = 0;j < broj_djevojaka;++j)
        if (matrica[i][j] && !djevojka[i] && !momak[j])
        {
          ++zenske_simpatije[i];
          ++muske_simpatije[j];
        }

    nasao = 0;

    for (i = 0;i < broj_djevojaka;++i)
      if (zenske_simpatije[i] == 1)
        for (j = 0;j < broj_djevojaka;++j)
          if (matrica[i][j] && !momak[j])
          {
            nasao = djevojka[i] = momak[j] = 1;
            break;
          }

    for (i = 0;i < broj_djevojaka;++i)
      if (muske_simpatije[i] == 1 && !momak[i])
        for (j = 0;j < broj_djevojaka;++j)
          if (matrica[j][i] && !djevojka[j])
          {
            nasao = djevojka[j] = momak[i] = 1;
            break;
          }

  } while (nasao);

  brojac = 0;

  for (i = 0;i < broj_djevojaka;++i)
    if (djevojka[i])
      funkcija[brojac++] = i;

  pocetak = brojac;

  for (i = 0;i < broj_djevojaka;++i)
    if (!djevojka[i])
      funkcija[brojac++] = i;

  max_parova = pocetak;
  rekurzija(pocetak,pocetak);

  printf("\nMaksimalni broj parova = %d\n",max_parova);

  return 0;
}

RAZRED2.PAS

program razred;
const
  MAX_DJEVOJAKA = 50;
  MAX_DUBINA = 100;
var
  i,j : integer;
  broj_djevojaka,max_parova : integer;
  pocetak,kraj : integer;
  djevojka,momak : array [1..MAX_DJEVOJAKA] of integer;
  zenske_simpatije,muske_simpatije : array [1..MAX_DJEVOJAKA] of integer;
  matrica : array [1..MAX_DJEVOJAKA,1..MAX_DJEVOJAKA] of boolean;
  queue : array [0..MAX_DUBINA - 1] of integer;
  nasao : boolean;

procedure ucitaj;
var
  i,j : integer;
  broj : integer;
  f : text;

begin
  for i := 1 to broj_djevojaka do
    for j := 1 to broj_djevojaka do
      matrica[i,j] := false;

  assign(f,'RAZRED.DAT');
  reset(f);

  readln(f,broj_djevojaka);

  for i := 1 to broj_djevojaka do
    while true do
      begin
        read(f,broj);
        if broj = 0 then
          break;
        matrica[i,broj] := true;
      end;

  close(f);
end;

procedure init_queue;
begin
  pocetak := MAX_DUBINA - 1;
  kraj := 0;
end;
procedure enqueue (broj : integer);
begin
  pocetak := (pocetak + 1) MOD MAX_DUBINA;
  queue[pocetak] := broj;
end;
function dequeue : integer;
begin
  dequeue := queue[kraj];
  kraj := (kraj + 1) MOD MAX_DUBINA;
end;
function queue_empty : boolean;
begin
  queue_empty := false;
  if (pocetak + 1) MOD MAX_DUBINA = kraj then
    queue_empty := true;
end;

procedure rijesi;
var
  i : integer;
  tko : integer;
  nasao,next : integer;
  brojac : integer;
  odakle : array [1..MAX_DJEVOJAKA] of integer;
  gotovo : boolean;

begin
  brojac := 0;
  gotovo := false;

  while true do
    begin
      init_queue;

      while true do
        begin
          inc(brojac);
          if brojac > broj_djevojaka then
            begin
              gotovo := true;
              break;
            end;
          if djevojka[brojac] = 0 then
            begin
              enqueue(brojac);
              break;
            end;
        end;

      if gotovo then
        break;

      for i := 1 to broj_djevojaka do
        odakle[i] := 0;

      nasao := 0;

      while true do
        begin
          if queue_empty then
            break;
          tko := dequeue;

          if tko <= broj_djevojaka then
            for i := 1 to broj_djevojaka do
              begin
                if matrica[tko,i] AND (odakle[i] = 0) then
                  begin
                    enqueue(broj_djevojaka + i);
                    odakle[i] := tko;
                  end;
              end
          else
            begin
              if momak[tko - broj_djevojaka] = 0 then
                begin
                  nasao := tko - broj_djevojaka;
                  break;
                end;
              enqueue(momak[tko - broj_djevojaka]);
            end;
        end;

      if nasao = 0 then
        continue;

      repeat
        next := djevojka[odakle[nasao]];
        momak[nasao] := odakle[nasao];
        djevojka[momak[nasao]] := nasao;
        nasao := next;
      until nasao = 0;

      brojac := 0;

    end;

end;

begin
  ucitaj;

  for i := 1 to broj_djevojaka do
    begin
      djevojka[i] := 0;
      momak[i] := 0;
    end;

  repeat
    for i := 1 to broj_djevojaka do
      begin
        zenske_simpatije[i] := 0;
        muske_simpatije[i] := 0;
      end;

    for i := 1 to broj_djevojaka do
      for j := 1 to broj_djevojaka do
        if matrica[i,j] AND (djevojka[i] = 0) AND (momak[j] = 0) then
          begin
            inc(zenske_simpatije[i]);
            inc(muske_simpatije[j]);
          end;

    nasao := false;

    for i := 1 to broj_djevojaka do
      if zenske_simpatije[i] = 1 then
        for j := 1 to broj_djevojaka do
          if matrica[i,j] AND (momak[j] = 0) then
            begin
              djevojka[i] := j;
              momak[j] := i;
              nasao := true;
              break;
            end;

    for i := 1 to broj_djevojaka do
      if (muske_simpatije[i] = 1) AND (momak[i] = 0) then
        for j := 1 to broj_djevojaka do
          if matrica[j,i] AND (djevojka[j] = 0) then
            begin
              djevojka[j] := i;
              momak[i] := j;
              nasao := true;
              break;
            end;
  until not nasao;

  for i := 1 to broj_djevojaka do
    if djevojka[i] = 0 then
      for j := 1 to broj_djevojaka do
        if matrica[i,j] AND (momak[j] = 0) then
          begin
            djevojka[i] := j;
            momak[j] := i;
            break;
          end;

  rijesi;
  max_parova := 0;

  for i := 1 to broj_djevojaka do
    if djevojka[i] <> 0 then
      inc(max_parova);
  writeln;
  writeln('Maksimalni broj parova = ',max_parova);

end.

RAZRED2.C

#include <stdio.h>

#define MAX_DJEVOJAKA 50
#define MAX_DUBINA 100

int broj_djevojaka;
int matrica[MAX_DJEVOJAKA][MAX_DJEVOJAKA];
int djevojka[MAX_DJEVOJAKA],momak[MAX_DJEVOJAKA];
int zenske_simpatije[MAX_DJEVOJAKA],muske_simpatije[MAX_DJEVOJAKA];

int pocetak,kraj;
int queue[MAX_DUBINA];

void ucitaj (void)
{
  int i,j;
  int broj;
  FILE *fp;

  for (i = 0;i < broj_djevojaka;++i)
    for (j = 0;j < broj_djevojaka;++j)
      matrica[i][j] = 0;

  fp = fopen("RAZRED.DAT","rt");

  fscanf(fp,"%d\n",&broj_djevojaka);

  for (i = 0;i < broj_djevojaka;++i)
    do
    {
      fscanf(fp,"%d",&broj);
      if (!broj)
        break;
      matrica[i][broj - 1] = 1;
    } while (1);

  fclose(fp);
}

void init_queue (void)
{
  pocetak = MAX_DUBINA - 1;
  kraj = 0;
}

void enqueue (int broj)
{
  pocetak = (pocetak + 1) % MAX_DUBINA;
  queue[pocetak] = broj;
}

int dequeue (void)
{
  int stari_kraj;

  stari_kraj = kraj;
  kraj = (kraj + 1) % MAX_DUBINA;

  return queue[stari_kraj];
}

int queue_empty (void)
{
  return ((pocetak + 1) % MAX_DUBINA == kraj);
}

void rijesi (void)
{
  int i;
  int tko;
  int nasao,next;
  int odakle[MAX_DJEVOJAKA];
  int brojac = -1,gotovo = 0;

  do
  {
    init_queue();

    do
    {
      if (++brojac == broj_djevojaka)
      {
        gotovo = 1;
        break;
      }
      if (djevojka[brojac] == -1)
      {
        enqueue(brojac);
        break;
      }
    } while (1);

    if (gotovo)
      break;

    for (i = 0;i < broj_djevojaka;++i)
      odakle[i] = -1;

    nasao = -1;

    do
    {
      if (queue_empty())
        break;
      tko = dequeue();

      if (tko < broj_djevojaka)
        for (i = 0;i < broj_djevojaka;++i)
        {
          if (matrica[tko][i] && odakle[i] == -1)
          {
            enqueue(broj_djevojaka + i);
            odakle[i] = tko;
          }
        }
      else
      {
        if (momak[tko - broj_djevojaka] == -1)
        {
          nasao = tko - broj_djevojaka;
          break;
        }
        enqueue(momak[tko - broj_djevojaka]);
      }

    } while (1);

    if (nasao == -1)
      continue;

    do
    {
      next = djevojka[odakle[nasao]];
      momak[nasao] = odakle[nasao];
      djevojka[momak[nasao]] = nasao;
      nasao = next;
    } while (nasao != -1);

    brojac = -1;

  } while (1);

}

int main (void)
{
  int i,j;
  int nasao;
  int max_parova = 0;

  ucitaj();

  for (i = 0;i < broj_djevojaka;++i)
    momak[i] = djevojka[i] = -1;

  do
  {
    for (i = 0;i < broj_djevojaka;++i)
      zenske_simpatije[i] = muske_simpatije[i] = 0;

    for (i = 0;i < broj_djevojaka;++i)
      for (j = 0;j < broj_djevojaka;++j)
        if (matrica[i][j] && djevojka[i] == -1 && momak[j] == -1)
        {
          ++zenske_simpatije[i];
          ++muske_simpatije[j];
        }

    nasao = 0;

    for (i = 0;i < broj_djevojaka;++i)
      if (zenske_simpatije[i] == 1)
        for (j = 0;j < broj_djevojaka;++j)
          if (matrica[i][j] && momak[j] == -1)
          {
            djevojka[i] = j;
            momak[j] = i;
            nasao = 1;
            break;
          }

    for (i = 0;i < broj_djevojaka;++i)
      if (muske_simpatije[i] == 1 && momak[i] == -1)
        for (j = 0;j < broj_djevojaka;++j)
          if (matrica[j][i] && djevojka[j] == -1)
          {
            djevojka[j] = i;
            momak[i] = j;
            nasao = 1;
            break;
          }

  } while (nasao);

  for (i = 0;i < broj_djevojaka;++i)
    if (djevojka[i] == -1)
      for (j = 0;j < broj_djevojaka;++j)
        if (matrica[i][j] && momak[j] == -1)
        {
          djevojka[i] = j;
          momak[j] = i;
          break;
        }

  rijesi();

  for (i = 0;i < broj_djevojaka;++i)
    if (djevojka[i] != -1)
      ++max_parova;

  printf("\nMaksimalni broj parova = %d\n",max_parova);

  return 0;
}