Ш
как ее решить
Size: a a a
2020 May 02
Ш
вродь нужно делать Бинпоиск и + что то
Ш
Говорят это эквивалентно решить следующую задачу: “есть ли в графе с весами (𝑤_𝑒−𝑥) отрицательный цикл" Где x это значения бинпоиска
Ш
может кто то пояснить почему
V🇺
может кто то пояснить почему
потому что прибавление константы c ко всем весам меняет средний вес любого цикла на c
Ш
потому что прибавление константы c ко всем весам меняет средний вес любого цикла на c
ааааа спасибо
Ш
потому что прибавление константы c ко всем весам меняет средний вес любого цикла на c
не знаете как можно решить быстрее чем за N * M * log ?
MB
не знаете как можно решить быстрее чем за N * M * log ?
алгоритм Карпа поиска цикла минимального среднено веса
Он описан тут https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BE%D1%82%D0%BC%D0%B5%D0%BD%D1%8B_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B5%D0%B3%D0%BE_%D0%B2%D0%B5%D1%81%D0%B0
В разделе "Алгоритм поиска цикла минимального среднего веса"
Он описан тут https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BE%D1%82%D0%BC%D0%B5%D0%BD%D1%8B_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B5%D0%B3%D0%BE_%D0%B2%D0%B5%D1%81%D0%B0
В разделе "Алгоритм поиска цикла минимального среднего веса"
V🇺
есть алгоритм Карпа, позволяющий убрать log
Ш
Спасибо большое
/¯
привет всем а в задаче найти цикл, у которого среднее арифметическое весов рёбер минимально
Howard
Ш
алгоритм Карпа поиска цикла минимального среднено веса
Он описан тут https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BE%D1%82%D0%BC%D0%B5%D0%BD%D1%8B_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B5%D0%B3%D0%BE_%D0%B2%D0%B5%D1%81%D0%B0
В разделе "Алгоритм поиска цикла минимального среднего веса"
Он описан тут https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BE%D1%82%D0%BC%D0%B5%D0%BD%D1%8B_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B5%D0%B3%D0%BE_%D0%B2%D0%B5%D1%81%D0%B0
В разделе "Алгоритм поиска цикла минимального среднего веса"
не знаете где можно найти эту задачу чтобы отослать код на проверку ?
ML
china
AO
Господа, решаю задачу на литкоде. Вроде решил, но есть момент, который полностью меня ступорнул
AO
Обьясните, плз, дебила, как такое может быть
AO
откуда тут 4?
AO
в дереве с 2 ветками
AO
Все, ребят, до меня дошло