Архив форума

Задачка с последней тренировки нашей команды (Московский контест). На соревнованиях мы ее не решили, да и сейчас идей новых не появилось. Может, человек, хорошо разбирающийся в графах, подскажет что-нибудь.
Вот условие:
Дан граф на тысячу вершин. Все ребра - с весом единица. Надо построить минимальный разрез из одной вершины в другую.

Честно говоря, кроме того, чтобы искать поток за O(N*N*N), ничего в голову не приходит. Хотя по времени, скорее всего, не пройдет...

Совсем не O(N^3), а O(N^2). Пустить N раз BFS.

И что нам даст этот BFS? Можно чуть подробнее?
PS А bfs разве работает за O(N)?