Всем привет!
Подумал, может на Сodeforces кто-то поможет найти ошибку\построить контрпример. Если помните паросочетания в недвудольных графах, то проблема Куна следующая: нам надо найти дополняющую цепь, но мы можем прийти в нужную вершину по ребру не того типа, пометить ее как посещенную и уйти.
Первая попытка решения проблемы: делаем dfs по вершинам типа
(v, flag), гдеflag– тип ребра, по которому мы пришли. Это, очевидно, не работает: мы можем пройти и через(v, false), и через(v, true), так как это разные вершины, но тогда наш дополняющий путь в исходном графе не простой, и мы на самом деле не нашли дополняющую цепь.Вторая попытка решения проблемы: делаем все то же самое, но в явном виде запрещаем dfs идти в вершины, которые уже посещены (находятся на пути от старта до текущей вершины), даже если они были пройдены с другим флагом. Что-то вроде
vis[v, flag] <- false для всех v, flag
path = []
dfs(v, flag):
vis[v, flag] = true
path.add(v)
for u : g[v], для которых (status[vu] != flag) && (u not in path) && (not vis[u, !flag]):
dfs(u, !flag)
path.pop()
Поскольку люди пишут сжатие соцветий, а я очень вряд ли умнее Эдмондса, который его придумал, то к моему «решению» есть контр-пример, либо оно просто долго работает, но я пока не осознал, почему. Надеюсь, что найдутся умные люди, которые каким-то чудом увидят этот пост и объяснят мне, где я не прав :)
I think it should be quite simple to find a counter-example to your implementation with just a stress test, but I don't remember any such test right away.
The very similar algorithm, but a bit more powerful, was discussed here, code. The important difference is that in linked code we jump over and don't mark as visited odd vertices on a path, while you explicitly mark all vertices visited (path.add(v) and u not in path).
If you shuffle graph edges and do multiple attempts to find an augmenting path, this algorithm works very well, and I got AC in multiple tasks about general matchings this way (and even once in PTZ camp something much more complicated, on skew-symmetric flows). E.g. Timus 1099, which aggregated tests for decades (I hope), can be solved with this approach quite easily. It's claimed above that there is a test family where it's hard to find matchings heuristically, but I haven't seen such a test family.