注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2132】【圈地计划】  

2014-05-05 09:09:19|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:【看起来好长的样子= =】给一个n*m的格子图的每一个格子染色,可以染黑白两色,染白色有一个价值,染黑色有一个价值,然后如果相邻每有一个格子和这个格子染相同的颜色+一个价值,问如何染色得到最大价值。

    0.0随机在bzoj的status找的题目。由于做了A+B了,所以对这题有很强的既视感....= =

    显然咱们可以把所有的价值都加上去,那么问题由得到最大的价值变成了抛弃最少的价值。然后这显然就是一个最小割模型。咱们先把格子黑白染色,设和S割在一起的黑色的格子是商业区,白色的格子是工业区,和T割在一起的黑色的格子是工业区白色的格子是商业区【为了使得相同的颜色的格子之间的边被断掉】,那么咱们给每一个格子看做一个点,S向每一个黑色格子连一条容量为Aij的边,白色格子连容量为Bij的边,然后每一个黑色格子向T连一条容量为Bij的边,每一个白色格子向T连一条容量为Aij的边。然后考虑相邻的问题,由于咱们转化了,所以咱们只需要向周围四个边连一条容量为Cij+Ci'j'【Ci'j'为相邻的那个点的】的边即可。然后求这个图的最大流即最小割,最后用总价值减去即可0.0

    为什么这样是正确的呢?0.0
    因为每一个割都可以构成一个方案,很显然按照咱们的表示方法,T割和S割的点之间的边都是被抛弃的代价Cij+Ci'j'【这两个点的都抛弃了】,然后对于T割的边,它断掉了和S相连的边,而实际上它也的确抛弃了Aij的代价。S割类似,所以这里就是正确的了。

=====================

program bzoj2132;
const maxe=400000;
maxn=20010;
type edge=record
v,w,pre:longint;
end;

var e:array[0..maxe]of edge;
v:array[0..maxn]of boolean;
que,d,last,cur:array[0..maxn]of longint;
c:array[0..110,0..110]of longint;
n,m,tot:longint;
ans:int64;

function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;

procedure addedge(u,v,w:longint);
begin
if (u=-1)or(v=-1) then exit;
inc(tot);e[tot].v:=v;e[tot].w:=w;
e[tot].pre:=last[u];last[u]:=tot;
inc(tot);e[tot].v:=u;e[tot].w:=0;
e[tot].pre:=last[v];last[v]:=tot;
end;

function bfs(s,t:longint):boolean;
var tmp,l,r,u:longint;
begin
fillchar(v,sizeof(v),false);
l:=0;r:=1;que[l]:=s;
d[s]:=0;v[s]:=true;
while l<r do
begin
u:=que[l];
tmp:=last[u];
while tmp<>-1 do
begin
if (e[tmp].w>0)and(not v[e[tmp].v])then
begin
d[e[tmp].v]:=d[u]+1;
v[e[tmp].v]:=true;
que[r]:=e[tmp].v;
inc(r);
end;
tmp:=e[tmp].pre;
end;
inc(l);
end;
exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var tmp,f,flow:longint;
begin
if (a=0)or(p=t)then exit(a);
tmp:=cur[p];
flow:=0;
while tmp<>-1 do
begin
if (e[tmp].w>0)and(d[e[tmp].v]=d[p]+1) then
begin
f:=dfs(e[tmp].v,min(e[tmp].w,a),t);
if f<>0 then
begin
dec(a,f);
dec(e[tmp].w,f);
inc(e[tmp xor 1].w,f);
inc(flow,f);
if a=0 then break;
end;
end;
tmp:=e[tmp].pre;
if tmp<>-1 then cur[p]:=e[tmp].pre;
end;
exit(flow);
end;

function dinic(s,t:longint):longint;
var ans,i:longint;
begin
ans:=0;
while bfs(s,t) do
begin
for i:=s to t do
cur[i]:=last[i];
ans:=ans+dfs(s,maxlongint,t);
end;
exit(ans);
end;

function cal(i,j:longint):longint;
begin
if (i<1)or(i>n)or(j<1)or(j>m) then exit(-1);
exit((i-1)*m+j);
end;

procedure init;
var i,j,k,u:longint;
begin
read(n,m);
tot:=-1;ans:=0;
fillchar(last,sizeof(last),255);
for i:=1 to n do
for j:=1 to m do
begin
read(k);ans:=ans+k;
if (i+j)and 1=0 then
addedge(0,cal(i,j),k)
else
addedge(cal(i,j),n*m+1,k);
end;
for i:=1 to n do
for j:=1 to m do
begin
read(k);ans:=ans+k;
if (i+j)and 1=0 then
addedge(cal(i,j),n*m+1,k)
else
addedge(0,cal(i,j),k);
end;
for i:=1 to n do
for j:=1 to m do
begin
read(c[i][j]);
u:=cal(i,j);
ans:=ans+(c[i][j] shl 2);
if (i=1)then dec(ans,c[i][j]);
if (i=n)then dec(ans,c[i][j]);
if (j=1)then dec(ans,c[i][j]);
if (j=m)then dec(ans,c[i][j]);
addedge(u,cal(i-1,j),c[i][j]+c[i-1][j]);
addedge(cal(i-1,j),u,c[i][j]+c[i-1][j]);
addedge(u,cal(i,j-1),c[i][j]+c[i][j-1]);
addedge(cal(i,j-1),u,c[i][j]+c[i][j-1]);
end;
ans:=ans-dinic(0,n*m+1);
write(ans);
end;

begin
init;
end.


  评论这张
 
阅读(27)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017