BZOJ 1934 [Shoi2007]Vote 善意的投票

发布于 2017-05-26  240 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1934

题意:n 个小朋友,每个同学选择睡不睡午觉,每个人自己都有一个希望的结果, 如果投的票和自己希望的不一样就会不高兴一次,每个人还有一堆好朋友,如果自己投的票和好朋友的意愿不一样也会不高兴一次... 最小不高兴次数和...


最小割... 建模方式是这样的:

  1. 源点向同意睡觉的连 1,不同意睡觉的向汇点连 1
  2. 好朋友间连 1 的双向边

为什么这么搞呢,蒟蒻也不知道,代码如下:

 


一个非常弱的准退役OIER