#P2057. [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

[SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

题目描述

幼儿园里有 nn 个小朋友打算通过投票来决定睡不睡午觉。

对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。

虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。

我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。

我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?

输入格式

第一行两个整数 n,mn,m。其中 nn 代表总人数,mm 代表好朋友的对数。

第二行 nn 个整数,第 ii 个整数代表第 ii 个小朋友的意愿:当它为 11 时表示同意睡觉,当它为 00 时表示反对睡觉。

接下来 mm 行,每行有两个整数 i,ji,j,表示 i,ji,j 是一对好朋友,我们保证任何两对 i,ji,j 不会重复。

输出格式

一行一个整数,即可能的最小冲突数。

3 3
1 0 0
1 2
1 3
3 2
1

提示

对于 100%100\% 的数据,2n3002\le n\le3001mn(n1)21\le m \le \frac{n(n-1)}2