Покрытие ориентированного ацикличного графа путями?

Revision ru3, by -dub-otrezkov-, 2024-05-12 10:43:44

Решая курс по подготовке к выпускным экзаменам, я столкнулся со следующей задачей: $$$\newline$$$ Даны $$$n$$$ коробок, каждая длиной $$$a_i$$$. Мы можем вкладывать одну коробку в другую, если размер внутренней хотя бы на 7 единиц меньше внешней, при этом в каждую коробку не могла быть вложена только одна другая, а также какждая коробка может быть вложена максимум в одну другую. Множество коробок, вложенных друг в друга, назовем блоком. В задаче просят расположить коробки так, чтобы минимизировать количество блоков. $$$\newline$$$ Очевидно, данную задачу можно решать следующим образом (и это решение точно будет правильным): строим граф, в котором будет ребро $$$i \rightarrow j$$$, если $$$a_i - 7 \ge a_j$$$, данный граф очевидно не будет иметь циклов. Теперь блок из вложенных друг в друга коробок будет выглядеть как какой-то путь в данном графе, значит, минимизировать количество блоков, это то же самое, что разбить данный граф на минимальное количество непересекающихся по вершинам путей. Это довольно известная задача, например тут описывается ее решение. $$$\newline$$$ Тем не менее, авторы задачи предлагают несколько другое, гораздо более простое решение: перебирать коробки по убыванию $$$a_i$$$, поддерживая множество блоков, для каждого из которых храним размер последней вложенной в него коробки, и пытаться жадно вложить текущую коробку в какой-нибудь блок. Если вложить никуда нельзя, то сделать новый блок, состоящий только из этой коробки. $$$\newline$$$ Данное решение интуитивно кажется мне некорректным, однако контртест я не смог придумать. К тому же, если данный жадник работает, любую задачу о покрытии графа путями можно сводить к задаче о коробках, после чего решать ее за $$$O(n \log n)$$$ вместо долгого решения паросочетаниями (а это бред какой-то). Буду благодарен, если кто-то подскажет, в чем проблема данного жадника и приведет контртест к нему.

Tags графы

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian -dub-otrezkov- 2024-05-12 10:43:44 15 (опубликовано)
ru2 Russian -dub-otrezkov- 2024-05-12 10:42:23 14
en2 English -dub-otrezkov- 2024-05-12 10:42:06 86
en1 English -dub-otrezkov- 2024-05-12 10:41:27 2104 Initial revision for English translation (saved to drafts)
ru1 Russian -dub-otrezkov- 2024-05-12 10:37:57 2059 Первая редакция (сохранено в черновиках)