#PQJ2765x16146. QOJ 2765_16146
QOJ 2765_16146
SHTSC’2007 Day 2 善意的投票 Vote 【问题描述】 幼儿园里有n 个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这 个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见, 但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我 们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来 意愿发生冲突的人数。 我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?
【输入格式】 文件的第一行只有两个整数n,m,保证有2≤n≤300,1≤m≤n(n-1)/2。 其中n 代表总人数,m 代表好朋友的对数。文件第二行有n 个整数,第i 个整 数代表第i 个小朋友的意愿,当它为1 时表示同意睡觉,当它为0 时表示反对睡 觉。接下来文件还有m 行,每行有两个整数i,j。表示i,j 是一对好朋友,我 们保证任何两对i,j 不会重复。
【输出格式】 只需要输出一个整数,即可能的最小冲突数。
【样例】 vote.in vote.out 3 3 1 0 0 1 2 1 3 3 2 1 6 6 1 1 1 0 0 0 1 2 2 3 4 2 3 5 5 6 2 (在第一个例子中,所有小朋友都投赞成票就能得到最优解;在第二个例子 中,所有小朋友都不按照自己的意愿投就可以得到最优解)