No.1776 Love Triangle 2 (Hard)
タグ : / 解いたユーザー数 7
作問者 :
hitonanode
Problem Statement
This problem shares its setting with No.1775 Love Triangle 2; only the time limit, the input constraints and test cases, and the output format differ.
At a certain school, student volunteers are planning a Christmas gift exchange party. The school has $N$ students, each represented by a student number $1, 2, \dots, N$. Students $A_i$ and $B_i$ are friends with each other $(i = 1, 2, \dots, M)$, and no other pair of $2$ students are friends with each other.
The $3$ organizers $X, Y, Z$ are especially close friends with one another, and all of them want to take part in the exchange party. They also hope that the party will create new connections, so they have decided that all participants will line up to form $1$ circle such that no two friends are adjacent and exchange gifts in it. What is the minimum number of participants required to hold the party they want? Also find an arrangement for the party.
Input
$N\ \ M$ $X \ \ Y \ \ Z$ $A_1\ \ B_1$ $A_2\ \ B_2$ $\vdots$ $A_M\ \ B_M$
- $3 \le N \le 150$
- $3 \le M \le \frac{N(N - 1)}{2}$
- $1 \le X < Y < Z \le N$
- $1 \le A_i < B_i \le N \ \ (i = 1, 2, \dots, M)$
- $A_i \neq A_j$ or $B_i \neq B_j \ \ (i \neq j)$
- $(A_1, B_1) = (X, Y),\, (A_2, B_2) = (X, Z),\, (A_3, B_3) = (Y, Z)$
- All inputs are integers.
Output
On line $1$, output "the minimum number $k$ of people needed to form a circle that includes the $3$ people $X, Y, Z$ and in which no two friends are adjacent". On line $2$, output "a circle that can actually be formed with $k$ people" as "a sequence of length $k + 1$ that starts with $X$ and ends with $X$", separated by spaces.
If there are multiple circles that can be formed with $k$ people, output the one for which the output sequence is lexicographically smallest.
If no such circle can be formed, output only $-1$ on line $1$.
Sample
Sample 1
Input
6 5 1 2 3 1 2 1 3 2 3 1 4 2 5
Output
6 1 5 3 4 2 6 1
Between students $1, 2, 3$, it is necessary to place $1$ student each from students $4, 5, 6$, so all $6$ students must participate. Noting that only students $5, 6$ can be adjacent to student $1$ and only students $4, 6$ can be adjacent to student $2$, a circle can be formed by lining up in the order $1\ 5\ 3\ 4\ 2\ 6\ 1$. The reversed circle $1\ 6\ 2\ 4\ 3\ 5\ 1$ also satisfies the conditions, but it is judged as incorrect because the lexicographically smallest one must be output.
Sample 2
Input
6 5 1 2 3 1 2 1 3 2 3 1 4 1 5
Output
-1
Only student $6$ can be adjacent to student $1$, so a circle cannot be formed.
Sample 3
Input
8 12 1 2 4 1 2 1 4 2 4 2 6 2 7 2 8 3 4 3 6 4 5 4 7 5 6 5 7
Output
7 1 3 2 5 8 4 6 1
Only students $3, 5$ can be adjacent to student $2$, and only students $6, 8$ can be adjacent to student $4$, so at least $7$ people are required. In fact, forming a circle in the order of the sample output achieves this with $7$ people, and it is the lexicographically smallest circle that can be formed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。