BZOJ 3894 文理分科

发布于 2017-09-04  297 次阅读


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

题意:n*m,每个格子可以染黑或者白,各有收益,一个格子相邻全黑和全白各有额外收益,求最大收益。


约定

文中出现形如 (i,j,k) 的三元组,意为连接一条从 i 到 j 的权值为 k 的边


考虑 S 割为黑色,T 割为白色。对于每个格子单独染色的建图是简单的:

(S,i, 黑收益)、(i,T, 白收益)

额外收益怎么处理呢?抽象一个点出来,一个 5 连通块的点连过去 inf,保证不会割掉,然后这个点连向 T。

这样处理了均为白色的额外收益,意为若有一个点连了 S,则必须割掉这个额外收益的边,黑色同理。

这样就可以了...

 


一个非常弱的准退役OIER