Забавно...но ты угадал) А "задачи как таковой нету" можно понимать как "я не уверен что существующая задача решается именно так".
и потом по fair play я не могу просто так дать сслыку на задачу и попросить решить)
1 2009-12-13 20:34:34
Re: Поиск радиуса графа. (23 ответов, оставленных в Problems)
2 2009-12-11 07:52:21
Re: Поиск радиуса графа. (23 ответов, оставленных в Problems)
Это да) спасибо.
P.S если кто-нибудь знает что-нибудь быстрее, отпишите пожалуйста)
3 2009-12-10 20:29:56
Re: Поиск радиуса графа. (23 ответов, оставленных в Problems)
Задачи как таковой нету, просто возник вопрос.
4 2009-12-10 14:59:16
Re: Поиск радиуса графа. (23 ответов, оставленных в Problems)
Подтверждаю. Граф двудольный. Ребра только между этими долями.
P.S хотя бы диаметр найти бы ^ ^
5 2009-12-09 15:52:44
Тема: Поиск радиуса графа. (23 ответов, оставленных в Problems)
Дан невзвешенный, неориентированный, связанный двудольный граф без кратных ребер.
Пусть D[x] - МАКСимальное из растояний от вершины х до всех остальных, тогда радиусом графа называется МИНимальное из всех D[x].
Требуется найти радиус графа. (кол-во вершин n < 10^4, кол-во ребер m < 10^5)
(Желательно быстрее чем за n^3)
Может быть кто нибудь расскажет алгоритм или скажет что это невозможно?
Большое спасибо.
P.S так как граф невзвешанный, под растоянием я понимаю минимальное кол-во ребер которое необходимо посетить.