"новая идея без жадной инициализации" — не совсем верно, ведь первая итерация внешнего цикла во внутреннем делает именно жадную инициализацию, сочетая каждую вершину с первым не тронутым (а значит — не сочтенным) соседом.

Если говорить про константные оптимизации, то как-то не комильфо каждый раз занулять массив used.

Я примерно такими хаками занимался на РОИ 2010 в задаче 3 про самолеты) Пихал Куна вместо того, чтобы решать задачу)

Сдавать сюда удобнее.

Интересно, а я всю жизнь так искал паросочетание и, кстати, всего раз получил ТЛ когда паросочетанием задача-таки сдавалась с алгоритмом Хопкрофта-Карпа. Правда, этот ТЛ был на простом новогоднем контесте, так что не очень считается :) Я, кстати, пару раз пытался сравнить с Диницем и все разы оно (паросочетание Куном) быстрее работало.

Прохладная история про эту оптимизацию.

В ПТЗ как-то была задача (H здесь), которая, по-видимому, задумывалась авторами как простая. Условием была не очень сильно замаскированная просьба посчитать паросочетание в двудольном графе с такими ограничениями: в каждой доле не более 10⁴ вершин, рёбер до 10⁵, мультитест из не более чем 10 тестов, ограничений на сумму чего бы то ни было по всем тестам нет. Особую пикантность добавляло отсутствие тайм-лимита в условии, потому что "как на финале".

Реакцию участников на эту задачу можно оценить по монитору, обратив особенное внимание на зелёный плюсик в первые полчаса (КНУ сдали ровно то, что написано в исходном посте). andrewzta картинно возмущался на всю аудиторию, что мол как же так — задача про паросочетание, ищу Хопкрофт-Карпом, а оно не заходит! (И ещё он обещал обучить этому алгоритму, кажется, итмо 2 или 3.)

Я верно понимаю, что в последней из приведенных версий парсоча нет смысла в жадной инициализации? Я протестил на паре задач, к которым были тесты — нигде не улучшает больше, чем на погрешность.

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

Еще есть эвристика в написании dfs'a. Вместо чего-то вроде

bool dfs(int v) {
    if (vis[v]) return false;
    vis[v] = true;
    for (int i = 0; i < (int)e[v].size(); i++) {
        if (mt[e[v][i]] == -1 || dfs(mt[e[v][i]])) {
            mt[e[v][i]] = v;
            return true;
        }
    }
    return false;
}

можно написать два одинаковых цикла: в первом поставить if (mt[e[v][i]] == -1), а во втором  –  if (dfs(mt[e[v][i]])). То есть, сначала проверить, нет ли ребра в вершину, не покрытую паросочетанием, и лишь если нет ни одной такой вершины, запускать dfs.

В сочетании с основным методом из поста это ускоряет в полтора раза на задаче, обсуждавшейся в этом комментарии.

Кто нибудь знает кем был Кун? Или какое у него имя? Или откуда он?