BZOJ 2127 happiness

发布于 2017-05-25  276 次阅读


题目链接: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 什么的想多了.... 最后发现智障错误连成了无向边....

 


一个非常弱的准退役OIER