Минимальное покрытие пути в ориентированном ациклическом графе

Вопрос, который я собираюсь здесь задать, уже задавался ранее при переполнении стека. Но я не могу правильно понять решения, опубликованные Skiminok.

Вот ссылка .

Я попробовал решение, размещенное по ссылке выше, с двумя заданными тестовыми примерами, но не смог получить правильный ответ.

Для тестового случая 1::

N=3 и K=2

5 4 7

DAG будет::

Примечание. Я построил приведенный выше DAG, учитывая:

Пусть pi и pj — две разные задачи. Тогда мы проведем направленное ребро от pi к pj тогда и только тогда, когда pj можно решить сразу после pi в тот же день последовательно. А именно, должны быть выполнены следующие условия:

i

|vi ​​- vj| >= K (рейтинговое требование).

Затем я построил двудольный граф, учитывая:

Для каждого ориентированного ребра (u, v) исходного DAG следует добавить неориентированное ребро (au, bv) к двудольному графу, где {ai} и { bi} — две части размера n.

Ответ = совпадение максимальной мощности в приведенном выше двудольном графе.

Соответствие максимального количества элементов в приведенном выше двудольном графе = 1 (Зеленый край)

Но ответ равен 2.

Аналогичный пример теста 2:

5 1

5 3 4 5 6

МАКС. мощность на приведенном выше графике БОЛЬШЕ ОДИН, но правильный ответ 1.

Я думаю, что я не реализую его правильно, пожалуйста, подскажите, где я делаю ошибку или есть какой-нибудь другой метод

Спасибо!