BZOJ 1934 [Shoi2007]Vote 善意的投票


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

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


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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1934 [Shoi2007]Vote 善意的投票


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,