Поиск максимального покрытия для двудольного сопоставления

Существует проблема Google Code Jam . Я узнал, что проблема решается с помощью Двудольного сопоставления. Но я не мог понять, как получить окончательный ответ, используя номер матча.
Вот sudo код

int match=0;
// Right - Right one String
// Left  - Left one String
for(int i=0;i<Right.size();i++)
match+=match_found(i)

Наконец, почему эти две строки кода

int need = match + (Right.size() + Left.size() - match * 2);
int answer = n- need;

Почему не должно быть answer = n-match

Пожалуйста, объясните это. Это было бы очень полезно.

1 ответ

  1. Из Википедии:

    Наименьшее реберное покрытие можно найти за полиномиальное время, найдя максимальное соответствие и расширяя его так, чтобы все вершины были покрыты

    Эта проблема требует найти минимальное количество ребер для покрытия всех вершин. Это равно количеству ребер в максимальном совпадении (match) плюс количество дополнительных ребер, которые необходимо добавить в жадное расширение.

    Максимальное совпадение охватывает 2 * совпадающие вершины, что означает, что должно быть x = (справа.size () + слева.размер () -2*совпадение) вершины все еще непокрыты.

    Поэтому нам нужно добавить x дополнительных ребер в процессе жадного расширения, и общее количество ребер соответствует+x.