P2057 [SHOI2007]善意的投票

    • 541通过
    • 1.1K提交
  • 题目提供者 shengmingkexue
  • 评测方式 云端评测
  • 标签 网络流 各省省选 2007 上海
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    幼儿园里有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不会重复。

    输出格式:

    只需要输出一个整数,即可能的最小冲突数。

    输入输出样例

    输入样例#1: 复制
    3 3
    1 0 0
    1 2
    1 3
    3 2
    输出样例#1: 复制
    1

    说明

    2≤n≤300,1≤m≤n(n-1)/2。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。