flow的解题报告.doc

4.引水入城
(flow.pas/c/cpp)
【问题描述】
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。
【输入】
输入文件名为flow.in。输入文件的每行中两个数之间用一个空格隔开。
输入的第一行是两个正整数N 和M，表示矩形的规模。
接下来N 行，每行M 个正整数，依次代表每座城市的海拔高度。
【输出】
输出文件名为flow.out。
输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。
【输入输出样例1】
flow.in flow.out
2 5
9 1 5 4 3
8 7 6 1 2
1
1
【样例1 说明】
只需要在海拔为9 的那座城市中建造蓄水厂，即可满足要求。
【输入输出样例2】
flow.in flow.out
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
1
3
【样例2 说明】
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
建造方法可能不唯一。
【数据范围】
本题共有10 个测试数据，每个数据的范围如下表所示：
测试数据编号能否满足要求 N M
1 不能 ≤ 10 ≤ 10
2 不能 ≤ 100 ≤ 100
3 不能 ≤ 500 ≤ 500
4 能 = 1 ≤ 10
5 能 ≤ 10 ≤ 10
6 能 ≤ 100 ≤ 20
7 能 ≤ 100 ≤ 50
8 能 ≤ 100 ≤ 100
9 能 ≤ 200 ≤ 200
10 能 ≤ 500 ≤ 500
对于所有的10 个数据，每座城市的海拔高度都不超过106。

题目分析：
在N*m的矩阵中，从第一行找出p个单元格，从这p个单元格出发，可以走遍最后一行的m个单元格。若存在，求p的最小值，不存在，则输出可以覆盖几个。其中，一个单元格可以走到另一个单元格的条件是该单元格的值大于另一个单元格。

策略：
1. 暴搜（无需对题目的性质进行分析）
本题数据量在n<=10,m<=10时无任何问题，可以过3个点。编程复杂度:容易

2. 连通分量来做，王老师上课时已讲过，但具体时间复杂度较大，编程技巧性较高，还有可能爆栈，在调试时无法做到ac，故本题应采用更为简单、可行、有效的方法。

3. 分析

（1）.对于每个数，作为一个节点，从高向低排。
对每个节点做一次扩展，向四周可达节点扩展。
性质0：第一层节点全部可达。
性质1：若当前节点没被达到，则说明周围没有节点可以到达，即孤点，达不到。
性质2：若当前节点被达到，则说明该点能够被灌溉到，可达，也可达到周围点。
做完一遍，最底层有点没被覆及到，则输出0，及这些点的个数。可以拿到3个点。

（2）性质3：一个点若能覆及下面的点，则这些点必然连续。
证明：
若最后一层每个节点都能访问到，
设节点4能控制最后一层3，5，
设节点5能控制最后一层4,5，6。
节点4到达最后一层5时经过的路径必与节点5到达最后一层4时经过的路径有一点重复，
性质成立。
对于每个点，记录覆盖最后一层某几个点的起始点，终止点，
最后Dp。可以拿到7个点。

总体算法：
1. (init)输入，并将n*m个元素化为各个节点，并存储为一维数组。
2.（sort）排序，将所有元素按高度从小到大排。
3. (floodfill)做一遍搜索。具体为：
  全布设为false，从最高点向最低点做，每做一点就向周围扩张，如果可以达到就设为true。
4.（fullcheck）判断，是否可以全部达到。可以判断最后一层是否全部为true。如不是，有几个为false
  就输出几个。
5. (edgefill)即判断最上层每个节点控制最下一层哪一段。
6.（printans）用贪心思路或动规思路求解。
标程(虽然有一点点长，但算法十分简单)：
program flow;
const d:array[1..4,1..2] of integer=((1,0),(0,1),(-1,0),(0,-1));
type
  bt=record
    h,x,y:longint;
  end;
  bt1=record
    l,r:longint;
  end;
var
  v:array[0..1000,0..1000] of 0..1;
  cover:array[0..1000,0..1000] of bt1;
  a:array[0..1000,0..1000] of longint;
  edge:array[0..1000000] of bt;
  ans:array[0..1000] of bt1;
  num,n,m,solve,i,j,maxr:longint;

procedure clo;
begin
  close(output);
  halt;
end;

procedure init;
var i,j:longint;
begin
  assign(input,'flow.in');
  reset(input);
  assign(output,'flow.out');
  rewrite(output);
  read(n,m);
  for i:=0 to m+1 do
    begin
      a[0,i]:=maxlongint;
      a[n+1,i]:=maxlongint;
    end;
  for i:=0 to n+1 do
    begin
      a[i,0]:=maxlongint;
      a[i,m+1]:=maxlongint;
    end;
  for i:=1 to n do
    for j:=1 to m do
      begin
        read(a[i,j]);
        edge[(i-1)*m+j].x:=i;
        edge[(i-1)*m+j].y:=j;
        edge[(i-1)*m+j].h:=a[i,j];
      end;
  close(input);
end;

procedure sort(l,r:longint);
var
  i,j,x:longint;
  y:bt;
begin
  i:=l;
  j:=r;
  x:=edge[(l+r)div 2].h;
  repeat
    while edge[i].h<x do inc(i);
    while edge[j].h>x do dec(j);
    if i<=j then
      begin
        y:=edge[i];
        edge[i]:=edge[j];
        edge[j]:=y;
        inc(i);
        dec(j);
      end;
  until i>j;
  if i<r then  sort(i,r);
  if l<j then  sort(l,j);
end;

procedure floodfill;
var q,p,i,j:longint;
begin
  fillchar(v,sizeof(v),0);
  for i:=1 to m do
    v[1,i]:=1;
  for i:=n*m downto 1 do
    if v[edge[i].x,edge[i].y]=1 then
      begin
        p:=edge[i].x;
        q:=edge[i].y;
        for j:=1 to 4 do
          if a[p,q]>a[p+d[j,1],q+d[j,2]] then
            v[p+d[j,1],q+d[j,2]]:=1;
      end;
end;

procedure fullcheck;
var i,sum:longint;
begin
  sum:=0;
  for i:=1 to m do
    if v[n,i]<>1 then inc(sum);
  if sum<>0 then
    begin
      writeln(0);
      writeln(sum);
      clo;
    end;
end;

procedure edgefill;
var i,j,p,q,minl,maxr:longint;
begin
  num:=0;
  for i:=1 to n*m do
    begin
      p:=edge[i].x;
      q:=edge[i].y;
      minl:=maxlongint;
      maxr:=0;
      if p=n then
        begin
          minl:=q;
          maxr:=q;
        end;
      for j:=1 to 4 do
        if (a[p,q]>a[p+d[j,1],q+d[j,2]]) then
          begin
            if (cover[p+d[j,1],q+d[j,2]].l<minl)and(cover[p+d[j,1],q+d[j,2]].l<>0) then
              minl:=cover[p+d[j,1],q+d[j,2]].l;
            if (cover[p+d[j,1],q+d[j,2]].r>maxr)and(cover[p+d[j,1],q+d[j,2]].l<>0) then
              maxr:=cover[p+d[j,1],q+d[j,2]].r;
          end;
      cover[p,q].l:=minl;
      cover[p,q].r:=maxr;
      if (p=1)and(minl<>maxlongint) then
        begin
          inc(num);
          ans[num].l:=minl;
          ans[num].r:=maxr;
        end;
    end;
end;

procedure sort1;
var
  i,j:longint;
  t:bt1;
begin
  for i:=1 to num-1 do
    for j:=i+1 to num do
      if (ans[i].l>ans[j].l)or
         ((ans[i].l=ans[j].l)and(ans[i].r>ans[j].r)) then
      begin
        t:=ans[i];
        ans[i]:=ans[j];
        ans[j]:=t;
      end;
end;

procedure printans;
begin
  i:=1;
  maxr:=1;
  solve:=0;
  sort1;
  repeat
    inc(solve);
    while (i<=num)and(ans[i].l<=maxr+1) do
      inc(i);
    dec(i);
    maxr:=ans[i].r;
  until maxr>=m;
  writeln(1);
  writeln(solve);
  clo;
end;

begin
  init;
  sort(1,n*m);
  floodfill;
  fullcheck;
  edgefill;
  printans;
end.

测试点
1
2
3
4
5
时间(s)
0.00
0.31
0.02
0.21
0.02
测试点
6
7
8
9
10
时间(s)
0.01
0.00
0.02
0.02
0.06

总结：本题对于动归、排序掌握程度要求较高，做完这两步，本题迎刃而解。
测试点：采用提高组标准，没有样例，较为刁钻。有n=1,和n=500,m=500的极端情况。
考虑到本题编写时间较长，虽算法简单，但完成步骤较多，故只有三个极端。