BZOJ 2127 happiness


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

题意:对于一个 n*m 的网格图,每个点有 a,b 两种收益选择,若点 (i,j) 与它相邻的点同时选择 a 或 b 有一个额外收益,求最大收益...


最小割的做法是比较显然的,建图的方法比较多... 博主莽了一发暴力建图...7500ms 卡过

将每个学生和每个“联动收益”抽象成点... 现在我们有了 5*n*m 个点....

对于每个选文的学生,源点连过去,对于每个 习武 选理的学生,连向汇点,边权为个人收益...

对于每组选文的收益,源点连过去,边权为该组收益,该收益再向对应的点连 inf...

对于每组选理的收益,连向汇点,边权为该组收益,对应的点再向该收益连 inf...

一口气码完,狂 WA 不止.... 果然 1A 什么的想多了.... 最后发现智障错误连成了无向边....

 

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

转载:转载请注明原文链接 - BZOJ 2127 happiness


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

标签: , ,