Ш
Всего в том королевстве было N городов, которые соединялись M двусторонними дорогами таким образом, что из любого города можно было проехать в любой другой.
Size: a a a
2020 March 08
Ш
M = N - 1
A
откуда следует, что M не может быть больше, чем N-1?
Ш
По условию
A
а, вот, вижу, это явно написано открытым текстом, да
DK
По условию
K
так это же максимальное паросочетание
A
ага
K
где там дп
DK
Я думал дп на поддереве но ничего нормального не получилось
Ну да, тут ДП по поддеревьям, думайте еще
K
стандартный алгоритм улучшения
DK
так это же максимальное паросочетание
Паросоч на дереве решается динамикой за линию
A
по идее на дереве паросочетания искать проще
K
Паросоч на дереве решается динамикой за линию
вполне верю
DK
Я думал дп на поддереве но ничего нормального не получилось
Ну то есть, я не вижу смысла особо подсказывать, когда вы уже сделали 70% умозаключений сами и осталось только сесть и dfs написать
K
только зачем динамика, если достаточно однопроходной рекурсии
Ш
Ну то есть, я не вижу смысла особо подсказывать, когда вы уже сделали 70% умозаключений сами и осталось только сесть и dfs написать
Да, я сейчас попробую
A
только зачем динамика, если достаточно однопроходной рекурсии
это примерно одно и то же в данном случае
A
Need help in this