2) Можно искать быстро (за O(m)), но это не совсем просто. Я знаю только алгоритм, который начинает с дробного паросочетания и постепенно округляет его до целого; хотя возможно есть что-то и попроще, по этой теме гуглится много разнообразных статей.

3) Нет^W Такого алгоритма науке неизвестно, доказано, что эта задача NP-complete.

О, у меня тоже есть один вопрос про паросочетания, с этими не связанный: есть задача про покрытие ориентированного ациклического графа минимальным количеством неперескающихся путей, её решение описано на е-максе. Допустим, что пути могут пересекаться, тогда достаточно просто транзитивно замкнуть исходный граф и воспользоваться предыдущим решением. Проблема в том, что решение первой задачи работает за , а второй уже за O(V^2.5). Вопрос — можно ли как-то использовать особый вид получившегося графа и ускорить решение?

4) каждый квадрат 4 на 4 обрабатываем отдельно — кладем либо два кирпича горизонтально либо вертикально

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

1) Можно попробовать применить min-cost-max-flow. Паросочетание минимальной стоимости за куб мы находить умеем, если использовать дейкстру с потенциалами. Искать дейкстрой путь, в котором максимальное ребро минимально, мы тоже умеем, но здесь уже не получится так халявно добавить потенциалы (у сложения есть обратная операция, а у взятия обратного — нет). Если мы научимся добавлять потенциалы/каким-то другим способом искать кратчайший путь за O(V²), то будет решение ра куб.

Собственно, соображение, по которому не должна работать никакая жадность: если бы жадность работала, то паросочетания минимального веса можно было бы искать почти такой же жадностью.

upd: А не правда, что построив паросочетание минимального суммарного веса, мы в случае евклидовой плоскости решим и исходную задачу?

̶1̶)̶ ̶В̶е̶н̶г̶е̶р̶с̶к̶и̶й̶ ̶а̶л̶г̶о̶р̶и̶т̶м̶ ̶р̶е̶ш̶и̶т̶ ̶э̶т̶у̶ ̶з̶а̶д̶а̶ч̶у̶ ̶з̶а̶ ̶к̶у̶б̶.̶ ̶Н̶а̶ ̶е̶м̶а̶к̶с̶е̶ ̶е̶с̶т̶ь̶ ̶ч̶т̶о̶ ̶п̶о̶ч̶и̶т̶а̶т̶ь̶ ̶п̶о̶ ̶э̶т̶о̶й̶ ̶т̶е̶м̶е̶.̶ В следующий раз обещаю внимательней читать условие...

1) Если паросочетание искать не Куном, а Диницем или алгоритмом Хопкрофта-Карпа, сложность будет O(N^(5/2)*log(N))

---придумал пример на котором не работает---

1) Подробностей не помню, но я точно писал какое то такое решение за точный куб: сортим все ребра по длине и запускаем куна. Как только не можем насытить вершину, то добавляем ребер до тех пор, пока не получится насытить. Если вспомню подробности — допишу.

upd. даже вот нашел задачу в архивах: http://acm.sgu.ru/problem.php?contest=0&problem=218

upd2. Ну вроде все. Когда насыщаем вершину, мы там строим дерево обхода бфс или дфс чтобы найти чередующуюся цепочку. Помечаем вершины обхода. Если не насытили — пробуем добавлять ребер, пока не добавим ребро из помеченой в непомеченную, запускаем дополнительный бфс/дфс по этому ребру (и опять же отмечаем вершины где побывали). И так далее. На одну насыщаемую вершину, в итоге получим чистый квадрат (потому что по сути у нас запуск одного бфс/дфс в несколько приемов). На весь алгоритм — чистый куб.

Как с паросочетаниями решать?