No.2286 Join Hands
タグ : / 解いたユーザー数 34
作問者 :
cureskol
sapphire__15
👑 Problem Statement
There are $N$ toddlers, and each toddler has two hands.
You make all the toddlers join hands by repeating the following procedure $N$ times.
- Choose two toddlers who each still have a hand that is not joined.
- Make the two chosen toddlers join their unjoined hands (if both of a toddler's hands are unjoined, either one may be used).
Note that in the end, no toddler is holding hands with themselves.
Now, there is a friendship list of toddlers consisting of $M$ pairs. The $i$-th pair in the list is $(u_i, v_i)$. If $(u, v)$ or $(v, u)$ is in the list, the $u$-th toddler and the $v$-th toddler are friends. Otherwise, the $u$-th toddler and the $v$-th toddler are not friends.
A toddler becomes happy when both hands are joined with friends, and becomes sad when both hands are joined with non-friends. A toddler with only one hand joined with a friend is neither happy nor sad.
Among all ways of joining hands, find the maximum value of $(\text{number of happy toddlers})-(\text{number of sad toddlers})$.
Input
$N \ M$ $u_1 \ v_1$ $\vdots$ $u_M \ v_M$
- All input values are integers.
- $2 \le N \le 5000$
- $0 \le M \le 5000$
- $1 \le u_i < v_i \le N$
- If $i \neq j$, then $(u_i, v_i) \neq (u_j, v_j)$.
Output
Output the answer, followed by a newline.
Sample
Sample 1
Input
6 3 1 2 1 3 4 5
Output
2
By having them join hands in the following order, the number of happy toddlers can be made $3$ and the number of sad toddlers $1$.
- Make $1$ and $2$ join hands.
- Make $1$ and $3$ join hands.
- Make $2$ and $6$ join hands.
- Make $3$ and $6$ join hands.
- Make $4$ and $5$ join hands.
- Make $4$ and $5$ join hands.
Since the number of happy toddlers cannot be made greater than the number of sad toddlers by $3$ or more, the answer is $2$.
Sample 2
Input
3 1 1 2
Output
-1
Note that no toddler can be holding hands with themselves.
Sample 3
Input
3 0
Output
-3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。