Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 27.05.2010, 13:36   #1
Bolik34
Новичок
Джуниор
 
Регистрация: 27.05.2010
Сообщений: 1
По умолчанию паросочетания

Здравствуйте!
У меня есть программа которую я скачал с интернета, она рабочая но я не знаю как она реализована...

Постановка задачи:
Имеется определенное кол-во мальчиков и девочек, скажем мальчику 1 нравиться девочка 2 и 3, а мальчику 2 нравиться девочка 2 и 1 и т.д.
нужно учесть все желания мальчиков и составить максимальное кол-во пар.

вот сам исходник:
paroco4etania.txt

-------------------------------------------------------------
Код:
const
  maxn = 2000;
var
  m,d,r,i,j,u,v,ans:longint;
  ne,use,was:array[1..maxn]of longint;
  e,p:array[1..maxn,1..maxn] of integer;
  ok,ok0:boolean;

procedure find(u:longint);
var
  i:longint;
begin
  if was[u]=1 then exit;
  if (u>m)and(use[u]=0) then begin
    use[u]:=1; ok:=true; exit;
  end;
  was[u]:=1;
  for i:=1 to ne[u] do if (u<=m)xor(p[u,e[u,i]]=1) then begin
    find(e[u,i]);
    if ok then begin
      p[u,e[u,i]]:=1-p[u,e[u,i]];
      p[e[u,i],u]:=1-p[e[u,i],u];
      use[u]:=1;
      exit;
    end;
  end;
end;

begin
  read(m,d,r);
  for i:=1 to r do begin
    read(u,v);
    inc(ne[u]); e[u,ne[u]]:=m+v;
    inc(ne[m+v]); e[m+v,ne[m+v]]:=u;
  end;
  for i:=1 to m do begin
    fillchar(was,sizeof(was[1])*(m+d),0);
    if use[i]=0 then
    begin ok:=false;find(i);
    end;
  end;
  for i:=1 to m do inc(ans,use[i]);
  writeln(ans);
  for i:=1 to m do if use[i]=1 then
  begin
    write(i,' ');
    for j:=1 to ne[i] do if p[i,e[i,j]]=1 then
    begin writeln(e[i,j]-m);break;
    end;
  end;
  readln;
  readln;
end.
-------------------------------------------------------------------------
Пожалуйста помогите разобраться, а точнее описать все выполняемые действия от и до.
Bolik34 вне форума Ответить с цитированием
Старый 27.05.2010, 14:13   #2
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Желания девочек в расчет не принимаются
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц