BZOJ 3894 文理分科


题目链接: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,则必须割掉这个额外收益的边,黑色同理。

这样就可以了...

 

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

转载:转载请注明原文链接 - BZOJ 3894 文理分科


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

标签: , ,