NOI2010海拔

2007: [Noi2010]海拔

Time Limit: 20 Sec  Memory Limit: 552 MB
Submit: 1302  Solved: 612
[Submit][Status]

Description

YT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。 小Z作为该市的市长，他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量，即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值，YT市市民认为爬坡是一件非常累的事情，每向上爬h的高度，就需要消耗h的体力。如果是下坡的话，则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数)，那么一个人经过这段路所消耗的体力是max{0, h}（这里max{a, b}表示取a, b两个值中的较大值）。 小Z还测量得到这个城市西北角的交叉路口海拔为0，东南角的交叉路口海拔为1(如上图所示)，但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下（即你可以任意假设其他路口的海拔高度），每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。

Input

第一行包含一个整数n，含义如上文所示。 接下来4n(n + 1)行，每行包含一个非负整数分别表示每一条道路每一个方向的人流量信息。输入顺序：n(n + 1)个数表示所有从西到东方向的人流量，然后n(n + 1)个数表示所有从北到南方向的人流量，n(n + 1)个数表示所有从东到西方向的人流量，最后是n(n + 1)个数表示所有从南到北方向的人流量。对于每一个方向，输入顺序按照起点由北向南，若南北方向相同时由西到东的顺序给出(参见样例输入)。

Output

仅包含一个数，表示在最理想情况下每天上班高峰期间所有人爬坡所消耗的总体力和（即总体力和的最小值），结果四舍五入到整数。

Sample Input

1

1

2

3

4

5

6

7

8

Sample Output

3

【样例说明】
样例数据见下图。

最理想情况下所有点的海拔如上图所示。

【数据规模】
对于20%的数据：n ≤ 3；

对于50%的数据：n ≤ 15；

对于80%的数据：n ≤ 40；

对于100%的数据：1 ≤ n ≤ 500，0 ≤ 流量 ≤ 1,000,000且所有流量均为整数。

HINT

Source

最小割

题解：

让这题给坑了--海拔不一定为整数……

其实每个点的海拔一定是0 or 1

证明：（声亦香）

如图，既然出发点海拔是0，终止点海拔是1，中间总有人流需要上坡，而我们的贪心思想是让尽量少的人流上坡，我们就要选择最少人流的道路，那么人流最少的道路就要让它的人流尽可能的上到与1齐平的位置，这样才能使后面更多的人流不需要上坡。如果当前决策的海拔在0到1之间，那么后面就会有人流在其基础上提升到1，而如果当前人流较小，总可以使当前海拔上到1，使决策更优。

这样问题就转化为，选取一些边，使得删掉它们后，s、t不连通（这是因为所有的人流都必须上升1），并且这些边的权值和最小。等等，这不就是最小割吗？

然后这又是平面图，因此构造其对偶图，求最短路……

这题80分还是很好拿的，spfa即可，满分算法即要求用heap+dijkstra，苦逼的p党啊，代码量骤增……

代码：

 const maxn=;
 type node=record
      from,go,next,w:longint;
      end;
 var  i,j,n,cnt,tot,t,x,s,l,r,y:longint;
      head,d,a,p:array[..maxn] of longint;
      v:array[..maxn] of boolean;
      e:array[..maxn] of node;
      num:array[..,..] of longint;
 procedure insert(x,y,z:longint);
  begin
    inc(tot);
    e[tot].from:=x;e[tot].go:=y;e[tot].w:=z;e[tot].next:=head[x];head[x]:=tot;
  end;
 procedure up(i:longint);
  var t:longint;
  begin
  while (i>) and (d[a[i]]<d[a[i>>]]) do
   begin
   t:=a[i];a[i]:=a[i>>];a[i>>]:=t;
   p[a[i]]:=i;p[a[i>>]]:=i>>;
   i:=i>>;
   end;
  end;
 procedure down(i:longint);
  var t,j:longint;
  begin
  j:=i<<;
  if (j<cnt) and (d[a[j+]]<d[a[j]]) then inc(j);
  while (j<=cnt) and (d[a[j]]<d[a[i]]) do
   begin
   t:=a[i];a[i]:=a[j];a[j]:=t;
   p[a[i]]:=i;p[a[j]]:=j;
   i:=j;j:=j<<;
   if (j<cnt) and (d[a[j+]]<d[a[j]]) then inc(j);
   end;
  end;
 procedure dijkstra;
  begin
  fillchar(d,sizeof(d),);
  fillchar(v,sizeof(v),false);
  d[s]:=;cnt:=;
  for i:= to n*n+ do begin inc(cnt);a[cnt]:=i;p[i]:=cnt;up(cnt);end;
  for j:= to n*n+ do
   begin
   x:=a[];a[]:=a[cnt];dec(cnt);down();
   v[x]:=true;
   i:=head[x];
   while i<> do
    begin
    y:=e[i].go;
    if not(v[y]) and (d[x]+e[i].w<d[y]) then
     begin
     d[y]:=d[x]+e[i].w;
     up(p[y]);
     end;
    i:=e[i].next;
    end;
   end;
  end;

 procedure init;
  begin
    readln(n);s:=;t:=n*n+;
    for i:= to n do for j:= to n do num[i,j]:=(i-)*n+j;
    for i:= to n+ do
     for j:= to n do
      begin
       readln(x);
       if i= then insert(num[i,j],t,x)
       else if i=n+ then insert(s,num[i-,j],x)
       else insert(num[i,j],num[i-,j],x);
      end;
    for i:= to n do
     for j:= to n+ do
      begin
       readln(x);
       if j= then insert(s,num[i,j],x)
       else if j=n+ then insert(num[i,j-],t,x)
       else insert(num[i,j-],num[i,j],x);
      end;
    for i:= to n+ do
     for j:= to n do
      begin
       readln(x);
       if i= then insert(t,num[i,j],x)
       else if i=n+ then insert(num[i-,j],s,x)
       else insert(num[i-,j],num[i,j],x);
      end;
    for i:= to n do
     for j:= to n+ do
      begin
       readln(x);
       if j= then insert(num[i,j],s,x)
       else if j=n+ then insert(t,num[i,j-],x)
       else insert(num[i,j],num[i,j-],x);
      end;
  end;
 procedure main;
  begin
    dijkstra;
    writeln(d[t]);
  end;
 begin
   assign(input,'input.txt');assign(output,'output.txt');
   reset(input);rewrite(output);
   init;
   main;
   close(input);close(output);
 end.