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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【vijos】【p1734】【网络流,平面图,最短路】【海拔】  

2014-03-03 18:24:30|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    Google浏览器傲娇,vijos一直乱码,导致咱最近都没有去vijos做题....换了火狐就可以上了....
    这题的意思咱们来梳理一下...
    给出一个N*N的平面图(所以就有(N+1)*(N+1)条边)并给出每一条边正向和反向的人流量,正向和反向经过人都要付出代价,单位代价为 max( 终止点的高度-出发点的高度,0),然后西北角和东南角的高度已经定下,要乃给其余的点都设一个高度,使得总代价最小。
    vijos的好处就是可以找分类题目做,缺点也就是一开始就知道了算法的范围.....
    网络流?
    不过看起来也应该像咩....
    首先排除下干扰...从a->b x个人,b->a y个人,就相当于 从 a->b x-y 个人
    咱感觉这应该是挺正常的吧...所以我们就把每一条边都转换成了只有一边有人,然后去求代价。
    然后咱突然发现了一个奇葩的想法....这货就是最小割了.....
    最小割左边的高度全部设为1,然后右边的全部设为0.这样答案就是最小割容量。
    但是这应该是最优的么?
    我们假设我们有了一个凹凸不平的方案,我们就可能得到一个凸起的或者凹进去的地方没有靠着边界的地方,很显然这个地方直接用脚踩平或者隆起来会更优,也就是说,每一个高度构成一个连通块。
    但是这也可能不对呵?由于高度可以分数,咱可以来三层连通块啊?1层高度1,1层高度0.5,1层高度0,但是设这两个割的 容量分别为 u,v 那么 总的花费就是 u*0.5+v*0.5,由于 u>=最小割 m ,v>=m 则 u*0.5+v*0.5>=m,这个方案绝对没有最小割优秀,推广下去,高度分别为 1,x1,x2,x3,x4...,xn,0(1>x1>x2>...>xn>0)的,也可以证明没有最小割优,至此这道题就可以AC了。


   啊啊啊,对了,忘记这题数据点数 10^4,所以还是像BZOJ1002那样平面图中最小割转换为最短路把....

   标号依旧是可以算的,我们给每一个矩形标号1~n*n,然后左上为0,右下为1,然后就是纠结加边的方向到底是怎么样的(很明显蒟蒻一直没有理解..),左上到右下的每一条路径都构成了一个割,考虑那些非正常向的边,它们显然是反向的。

  去百度了一下题解,发现咱想的差不多正确了,正准备写SPFA,发现一群神犇们的前车之鉴,果断写的dij+堆,Seter神犇说zkw线段树其实更爽一些(作为蒟蒻,咱也觉得...)

  然后此题傻×的 数组开小了,另外又一次没看 容量范围 为10^6 ,开的longint(c++的int),开Int64就可以过了。
====================================================

program vijosp1734;
const maxn=300010;
type
  edge=record
  v,w,pre:longint;
  end;

var tot,n:longint;
    e:array[0..maxn shl 2]of edge;
    last:array[0..maxn]of longint;
    h,st:array[0..maxn]of longint; {h就是堆,存的是指向d的指针(实际上就是下标)}{st是某个点在堆的位置}
    d:array[0..maxn]of int64;

function calc(i,j:longint):longint;
begin
  if i=0 then exit(0);
  if i=n+1 then exit(n*n+1);
  if j=0 then exit(n*n+1);
  if j=n+1 then exit(0);
  exit((i-1)*n+j);
end;

procedure down(p:longint);
var x,j:longint;
begin
  x:=h[p];
  j:=p shl 1;
  while j<=tot do
   begin
     if (j<tot)and(d[h[j]]>d[h[j+1]])then inc(j);
     if (d[h[j]]>=d[x]) then j:=tot+1
                       else begin
                            h[p]:=h[j];
                            st[h[j]]:=p;
                            p:=j;
                            j:=j shl 1;
                            end;
   end;
  h[p]:=x;
  st[x]:=p;
end;

procedure up(p:longint);
var x,j:longint;
begin
  x:=h[p];
  j:=p shr 1;
  while j>0 do
   begin
     if (d[h[j]]<=d[x]) then j:=0
                        else begin
                             h[p]:=h[j];
                             st[h[j]]:=p;
                             p:=j;
                             j:=j shr 1;
                             end;
   end;
  h[p]:=x;
  st[x]:=p;
end;

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

procedure dijkstra;
var i,j,tmp:longint;
begin
  fillchar(d,sizeof(d),1);
  fillchar(st,sizeof(st),0);
  d[0]:=0;
  tot:=1;
  h[tot]:=0;st[0]:=1;
  while tot>0 do
   begin
     j:=h[1];h[1]:=h[tot];h[tot]:=j;
     dec(tot);
     down(1);
     tmp:=last[j];
     while tmp<>0 do
      begin
        if d[e[tmp].v]>d[j]+e[tmp].w then
         begin
           d[e[tmp].v]:=d[j]+e[tmp].w;
           if st[e[tmp].v]=0 then
            begin
              inc(tot);
              h[tot]:=e[tmp].v;
              st[e[tmp].v]:=tot;
            end;
           up(st[e[tmp].v]);
         end;
        tmp:=e[tmp].pre;
      end;
   end;
end;

procedure init;
var i,j,x:longint;
begin
  read(n);
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to n+1 do
   for j:=1 to n do
    begin
      read(x);
      addedge(calc(i-1,j),calc(i,j),x);
    end;
  for i:=1 to n do
   for j:=1 to n+1 do
     begin
       read(x);
       addedge(calc(i,j),calc(i,j-1),x);
     end;
  for i:=1 to n+1 do
    for j:=1 to n do
     begin
       read(x);
       addedge(calc(i,j),calc(i-1,j),x);
     end;
  for i:=1 to n do
    for j:=1 to n+1 do
     begin
       read(x);
       addedge(calc(i,j-1),calc(i,j),x);
     end;
  n:=n*n+1;
  dijkstra;
  write(d[n]);
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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