Занятие 18

Пусть дан некоторый невзвешенный неориентированный граф. Паросочетанием в этом графе называется такое подмножество его рёбер, что никакие два ребра не смежны. Максимальное же паросочетание – это паросочетание, в котором максимальное возможное количество рёбер. Алгоритм поиска максимального паросочетания в произвольном графе есть достаточно сложная, хотя и решаемая с полиномиальной сложностью задача.

Для двудольных графов (у которых существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям) существуют довольно простые и эффективные алгоритмы для нахождения максимального паросочетания.

Наиболее известная задача на применение подобных алгоритмов имеет следующую формулировку: "Имеется `X` мальчиков и `Y` девочек. Каждый согласен танцевать на балу только с определёнными индивидами противоположного пола, причём это отношение коммутативно – если мальчик согласен танцевать с какой-то девочкой, то она тоже согласна танцевать с ним и наоборот. Организаторам бала необходимо набрать наибольшее количество пар на танец. Логично, что каждая персона танцует не более, чем с одним другим".

На основе данных задачи можно построить двудольный граф, в котором вершины одной доли обозначают мальчиков, а другой – девочек. Две вершины соединяются ребром, если соответствующие мальчик и девочка согласны танцевать друг с другом. Построив в данном графе максимальное паросочетание, мы и сформируем необходимое множество пар.

Этот алгоритм ищет максимальное паросочетание в неориентированном невзвешенном двудольном графе, представленном на матрице смежности двудольного графа за время `O(N^3)`.

Алгоритм использует для построение паросочетания так называемый метод чередующихся цепочек. Начнём строить наше паросочетание, последовательно прибавляя к нему всё больше и больше рёбер, пока не придём к ситуации, что текущее паросочетание максимально и больше добавить рёбер нельзя. Покрасим рёбра, входящие в текущее паросочетание в зелёный цвет. Рёбра, не входящие в текущее паросочетание покрасим в чёрный цвет. Изначально в графе все рёбра чёрные, т.к. мы ещё не начинали строить паросочетание.

Назовём вершину графа свободной, если из неё не выходит зелёных рёбер. Назовём некоторый простой путь из рёбер с цветами чёрное-зелёное-…-чёрное чередующейся цепочкой, если первая и последняя его вершины свободны.

Теперь будем делать следующее: находим любую чередующаяся цепочку и перекрашиваем все её рёбра в противоположный цвет. Очевидно, что впоследствии такого действия количество зелёных рёбер увеличится на один, а их множество по-прежнему будет задавать некоторое (пока, возможно, не максимальное) паросочетание. Так делаем до тех пор, пока все чередующиеся цепочки не исчезнут. Утверждение: к этому моменту множество зелёных рёбер будет задавать максимальное паросочетание.

Теперь вся проблема свелась к тому, как искать чередующиеся цепочки. В качестве потенциального начала следующей цепочки будем перебирать последовательно все вершины одной из долей графа, а потом пытаться найти цепочку, выходящую из этой вершины. Для успешного проведения подобных действий нам понадобится дополнительный массив меток Use: array[0..MaxX] of Boolean и массив P: array[1..MaxY] of Integer, в котором мы будем хитрым образом хранить текущее состояние "зелёности" рёбер.

Действительно, как нам лучше хранить информацию о зелёных рёбрах, в данный момент присутствующих в графе? Можно, конечно, в матрице смежности двудольного графа хранить не True и False в зависимости от наличия ребра, а хранить, скажем, 0 для отсутствия ребра, 1 для чёрного и 2 для зелёного ребра. Но это неудобная и неоптимальная фишка, забейте на неё.

Чтобы придумать более хитрый метод хранения, надо сначала слегка подумать, а потом заметить вот что: из одной вершины может выходить не более одного зелёного ребра. Действительно, если из одной вершины выходит два зелёных ребра, то они однозначно смежны, что противоречит понятию паросочетания. Таким образом мы можем сделать следующее: будем хранить 0 в элементе массива P[I], если из I-ой вершины одной доли не выходит зелёных рёбер, а если зелёное ребро выходит в вершину с номером K другой доли, то положим P[I] равным K. И вот ещё что: для реализации алгоритма нам понадобится массив P лишь для вершин второй доли, поэтому его размерность равна MaxY. Таким образом, если, скажем, P[1] = 3, это значит, что из первой вершины второй доли выходит зелёное ребро в третью вершину первой доли.

int setl[L],setr[R];
int nl,nr;
bool can[L][R];
bool use[L];

bool trySet(long v)
{
  if(use[v]) return 0;
  use[v]=1;
  for(int i=0; i<nr; ++i)
    if(can[v][i] && (setr[i]<0 || trySet(setr[i])))
    { 
      setl[v]=i;
      setr[i]=v;
      return 1;
    }
  return 0;
}
int maxMatch()
{ 
  int k=0;
  for(int i=0; i<nl; ++i)
    setl[i]=-1;
  for(int i=0; i<nr; ++i)
    setr[i]=-1;
  for(int i=0;i<nl;++i)
  {
    for(int j=0; j<nl; ++j)
      use[j]=0;
    if(trySet(i))
      ++k;
  }
  return k;
}