Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Delphi]поиск максимального паросочетания

Автор: denks 16.5.2008, 20:27

Здравствуйте. Передо мной поставлена задача реализовать программу нахождения максимального паросочетания в двудольном графе. Поискав в интернете нашёл вот такой вот код

Код


program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
const
  m = 200;
  n = 200;

var
  a: array [1..n, 1..m] of boolean;
  v: array [1..n] of boolean;
  p: array [1..m] of word;
  c, mm, nn: longint;

procedure init;
var
  x, y, k, i: longint;
begin
  fillchar(a, sizeof(a), 0);
  fillchar(v, sizeof(v), 0);
  fillchar(p, sizeof(p), 0);
  c := 0;

  assign(input, 'matching.in');
  reset(input);

  read(nn, mm, k);

  for i := 1 to k do
  begin
    read(x, y);
    a[x, y] := true;
  end;
end;

function find_pair(k: integer): boolean;
var
  i: integer;
begin
  find_pair := false;

  if v[k] then
    exit;

  v[k] := true;

  for i := 1 to mm do
    if a[k, i] and ( (p[i] = 0) or find_pair(p[i]) ) then
    begin
      find_pair := true;
      p[i] := k;
      exit;
    end;
end;

procedure solve;
var
  i: longint;
begin
  for i := 1 to nn do
  begin
    fillchar(v, sizeof(v), false);
    if find_pair(i) then
      inc(c);
  end;
end;

procedure done;
var
  i: longint;
begin
  writeln(c);
  for i := 1 to mm do
    if p[i] <> 0 then
      writeln(i, ' ', p[i]);
end;


begin
  init;
  solve;
  done;
end.

Файл matching.in выглядит следующим образом

Код

Собственно что говоря не понятно. вот здесь нашёл объяснение алгоритма http://www.progz.ru/forum/lofiversion/index.php/t1952.html
Но не совсем понятно почему так вершины представлены буквами, а в моём случае это цифры.
Так же нашёл следующий визуализатор по этой теме http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/alt-chains-2002
Но опять же не могу найти связи между программой код которой я нашёл, и тем что показано в визуализаторе.
Помогите пожалуйста разобраться с этим. Как осуществлять ввод ? И пожалуйста если кто-то знает покажите на примере кода который я дал контрольный пример как это работает.

M
Rodman

Модератор: Название темы должно cодержать язык написания!
Модератор: Используйте корректную подсветку кода!