Перестановка на графиках

Question

В строке есть N учеников. Мы хотим взять лучшее фото. Фото считается лучшим, когда максимальное количество студентов удовлетворено. Студент удовлетворен, если он является правым соседом своего лучшего друга. У каждого ученика есть только один лучший друг. Вы должны найти количество довольных учеников в лучшей фотографии и количество лучших лучших фотографий.

подход:

.

• каждый узел находится в цикле. (каждый узел имеет ровно один входящий и один исходящий край). Здесь мы можем удовлетворить все узлы, кроме одного (крайний левый узел). Таким образом, удовлетворенными узлами являются N-1, а разными вариантами являются N

• , которые имеют по крайней мере один входящий фронт, могут удовлетворять точно одному узлу. Таким образом, легко вычислить количество удовлетворенных узлов. Сделаем массив B, где B [i] - количество входящих ребер i. Тогда другой способ удовлетворить максимальное количество узлов - это продукт B_s. Но есть некоторые варианты «BAD»,, где все узлы цикла удовлетворены. Но мы можем легко вычесть варианты «BAD». В вариантах «BAD» для узлов цикла мы точно знаем, кого они удовлетворяют. Такие разные варианты будут:

  B [K1] * B [K2] .... B [Kn] - B [P1] * B [P2] .... B [Pm]

где K - это массив узлов в компоненте (который имеет по крайней мере 1 входящее ребро), а P - это массив узлов, которые не находятся в цикле этого компонента (которые имеют по крайней мере 1 входящий край).

Я не мог понять концепцию Bad вариантов, почему мы их вычитаем.

Просьба Объяснить и может ли я найти полезные ссылки для этого типа проблем

Answer 1

Я бы предпочел написать еще одну редакционную статью, чем попытаться выяснить, что происходит с этим.

Подготовить ориентированный граф «лучших друзей», где каждая вершина является студентом, и каждый студент имеет дугу своему лучшему другу. Извлеките слабосвязные компоненты этого графа. В каждом компоненте мы можем удовлетворить всех, кроме одного ученика, но только в том случае, если учащиеся этого компонента стоят смежно. Таким образом, мы можем определить количество возможностей для каждого компонента, умножить их вместе и умножить на число перестановок числа компонентов (т. Е. Число компонентов факториала).

Для данного компонента есть две возможности. Первая возможность состоит в том, что одна вершина точно не имеет входящих дуг, одна вершина имеет ровно две, а остальные - одну. Бывший студент должен быть самым правым, поэтому существует одно действительное соглашение. Вторая возможность состоит в том, что все вершины имеют ровно одну входящую дугу. В этом случае количество действительных аранжировок равно числу вершин в компоненте (произвольно выбирайте самого правого студента, а затем обходите цикл).