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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【HOJ2739】【Matrix3】  

2014-03-27 18:13:19|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  题目大意:一个矩阵,每一个格子有高度和权值,然后可以每一次选择一个格子,然后往低处走,然后取走格子里面的权值,每个格子只能取一次,然后问最大获利。 
   限制增广次数的最大费用流...
  然后就是练习 zkw 费用流,zkw最大费用流怎么做?首先先把边权取反,然后用spfa预处理出zkw的dist[]标号而不是一开始的初始化为0。然后求出最小费用之后取反即可。
===================================

const maxn=7010;
      maxm=70010;
type edge=record
     u,v,w,c,pre:longint;
     end;

var a,h,num:array[0..55,0..55]of longint;
    e:array[0..maxm]of edge;
    d,slack,v,last,que:array[0..maxn]of longint;
    tot,k,cost,t,m,n,time:longint;

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

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

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

function modify:boolean;
var i,imp:longint;
begin
  imp:=maxlongint;
  for i:=0 to n*n shl 1+1 do
   if v[i]<>time then
    begin
      imp:=min(imp,slack[i]);
      slack[i]:=maxlongint;
    end;
  if imp=maxlongint then exit(true);
  for i:=0 to n*n shl 1+1 do
   if v[i]<>time then
    inc(d[i],imp);
  exit(false);
end;

procedure spfa(s:longint);
var l,r,tmp,u:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(d,sizeof(d),1);
  fillchar(v,sizeof(v),0);
  l:=0;r:=1;d[s]:=0;
  que[l]:=s;v[s]:=1;
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
       if (e[tmp].w>0)and(d[e[tmp].v]>d[u]+e[tmp].c) then
        begin
          d[e[tmp].v]:=d[u]+e[tmp].c;
          if v[e[tmp].v]=0 then
           begin
             que[r]:=e[tmp].v;
             r:=(r+1)mod maxn;
             v[e[tmp].v]:=1;
           end;
        end;
       tmp:=e[tmp].pre;
      end;
     l:=(l+1)mod maxn;
     v[u]:=0;
   end;
end;

procedure init;
var i,j,maxflow:longint;
begin
  read(n,k);
  fillchar(last,sizeof(last),255);
  tot:=-1;
  m:=n*n shl 1+1;
  for i:=1 to n do
   for j:=1 to n do
    begin
     read(a[i][j]);
     num[i][j]:=(i-1)*n+j;
     addedge(num[i][j] shl 1-1,num[i][j] shl 1,1,-a[i][j]);
     addedge(num[i][j] shl 1-1,num[i][j] shl 1,1<<20,0);
     addedge(0,num[i][j] shl 1-1,1<<20,0);
     if (i=1)or(i=n)or(j=1)or(j=n) then
       addedge(num[i][j] shl 1,m,1<<20,0);
    end;
  for i:=1 to n do
   for j:=1 to n do
     read(h[i][j]);
  for i:=1 to n do
   for j:=1 to n do
    begin
     if (i>1)and(h[i-1][j]<h[i][j])then
       addedge(num[i][j] shl 1,num[i-1][j] shl 1-1,1<<20,0);
     if (i<n)and(h[i+1][j]<h[i][j])then
       addedge(num[i][j] shl 1,num[i+1][j] shl 1-1,1<<20,0);
     if (j>1)and(h[i][j-1]<h[i][j])then
       addedge(num[i][j] shl 1,num[i][j-1] shl 1-1,1<<20,0);
     if (j<n)and(h[i][j+1]<h[i][j])then
       addedge(num[i][j] shl 1,num[i][j+1] shl 1-1,1<<20,0);
    end;
  spfa(0);
  cost:=0;
  maxflow:=0;
  time:=0;
  fillchar(v,sizeof(v),0);
  for i:=0 to n*n shl 1+1 do slack[i]:=maxlongint;
  repeat
    inc(time);
    maxflow:=maxflow+dfs(0,maxlongint,m);
    if k=0 then break;
  until modify;
  writeln(-cost);
end;

begin
  read(t);
  for t:=1 to t do
    init;
end.


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

历史上的今天

评论

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

页脚

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