P2057 [SHOI2007] Kind-Hearted Voting / [JLOI2010] Champion Survey

In a kindergarten, there are $n$ children who plan to decide whether to take a nap by voting. This issue is not very important to them, so they decide to be considerate. Although everyone has their own preference, they may cast a vote opposite to their original intention to accommodate their friends. We define the conflict count of a voting result as the sum of the following two quantities: - The number of friend pairs whose actual votes differ. - The number of children whose actual vote differs from their original preference. Our problem is: how should each child vote to minimize the conflict count?

The first line contains two integers $n, m$, where $n$ is the total number of children and $m$ is the number of friend pairs. The second line contains $n$ integers. The $i$-th integer is the $i$-th child’s preference: $1$ means agreeing to take a nap, and $0$ means opposing it. The next $m$ lines each contain two integers $i, j$, indicating that $i$ and $j$ are a pair of friends. We guarantee that any pair $i, j$ does not repeat.

Output a single integer on one line: the minimum possible conflict count.

For $100\%$ of the testdata, $2 \le n \le 300$, $1 \le m \le \frac{n(n-1)}{2}$. Translated by ChatGPT 5