147
правок
Изменения
м
mtmatching[to] = v;
mtmatching.assign (k, -1); for (int v u = 0; v u < n; vu++)
Нет описания правки
: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и из вершины <tex>x</tex> появилась дополняющая цепь.
: Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из <tex>x</tex> существовала и в исходном паросочетании.<br><br>
: Пусть <tex>p</tex> – {{---}} ближайшая к <tex>x</tex> вершина, которая принадлежит и новой дополняющей цепи и цепи <tex>(y \rightsquigarrow z)</tex>.
: Тогда <tex>MP</tex> - последнее ребро на отрезке <tex>(y \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>NP</tex> - последнее ребро на отрезке <tex>(z \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>QP</tex> - последнее ребро лежащее на отрезке <tex>(x \rightsquigarrow p)</tex> новой дополняющей цепи(см. Рисунок 1).<br><br>
: Допустим <tex>MP</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP</tex> ему не принадлежит.<br>
: Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>
: Функция <tex>dfs(v)</tex> {{---}} обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.
: В массиве <tex>mtmatching</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, mtmatching[i])</tex>.
{
int to = g[v][i];
if (mtmatching[to] == -1 || dfs(mtmatching[to]))
{
return true;
}
{
... чтение графа ...
{
used.assign(n, false);
dfs(vu);
}
for (int i = 0; i < k; i++)
if (mtmatching[i] != -1)
... вывод ...
