NOIP 2010 引水入城

一般可以想到对每一个第一行的点做BFS，然后记录从它开始泵水可以到达的最下方的城市。

需要明白一点，如果有一个BFS出的可到达的底端城市不是连续的，那么一定有城市不能得到水。因为中间一定存在几个高于旁边的城市,阻止了水的流动。

既然有解时从每个点可以到达的底端的点组成的是一个连续的区间，因此，问题转化为线段覆盖，可以用贪心解决。

90分代码：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <limits.h>
004 #include <string.h>
005 #define MXN 510
006 #define LENGTH 600000
007
008 int di[4] = {0,1,0,-1};
009 int dj[4] = {-1,0,1,0};
010
011 typedef struct point
012 {
013     int i,j;
014 }point;
015
016 typedef struct segment
017 {
018     int l,r;
019 }segment;
020
021 int arrive[MXN];
022 long h[MXN][MXN];
023 segment range[MXN];
024 point queue[LENGTH + 1];  //使用循环队列，否则可能会溢出
025 long head,tail;
026
027 int M,N;
028
029 void enqueue(point p)
030 {
031     queue[tail] = p;
032     tail = (tail + 1) % LENGTH;
033 }
034
035 point dequeue()
036 {
037     point r = queue[head];
038     head = (head + 1) % LENGTH;
039     return r;
040 }
041
042 segment flow(int p)
043 {
044     int k;
045     point now,next;
046     now.i = 1;
047     now.j = p;
048     head = tail = 0;
049     enqueue(now);
050     while(head < tail)
051     {
052         now = dequeue();
053         if(now.i == N)
054         {
055             arrive[now.j] = 1;
056         }
057         for(k = 0;k < 4;k ++)
058         {
059             if(h[now.i + di[k]][now.j + dj[k]] < h[now.i][now.j])
060             {
061                 next.i = now.i + di[k];
062                 next.j = now.j + dj[k];
063                 enqueue(next);
064             }
065         }
066     }
067     segment r;
068     for(r.l = 0;r.l <= M && arrive[r.l] == 0;r.l ++);
069     for(r.r = r.l;r.r <= M && arrive[r.r] == 1;r.r ++);
070     r.r -= 1;
071     if(r.r < r.l)    r.r = r.l = 0;
072     return r;
073 }
074
075 void mark(int p)
076 {
077     int k;
078     point now,next;
079     now.i = 1;
080     now.j = p;
081     head = tail = 0;
082     enqueue(now);
083     while(head < tail)
084     {
085         now = dequeue();
086         if(now.i == N)
087         {
088             printf("%d\n",now.j);
089             arrive[now.j] = 1;
090         }
091         for(k = 0;k < 4;k ++)
092         {
093             if(h[now.i + di[k]][now.j + dj[k]] < h[now.i][now.j])
094             {
095                 next.i = now.i + di[k];
096                 next.j = now.j + dj[k];
097                 enqueue(next);
098             }
099         }
100     }
101 }
102
103 void count()
104 {
105     int i;
106     int j;
107     int unable;
108     memset(arrive,0,sizeof(arrive));/*
109     for(i = 1;i <= M;i ++)
110     {
111         mark(i);
112     }*/
113     for(i = 1;i <= M;i ++)
114         for(j = range[i].l;j <= range[i].r;j ++)
115             arrive[j] = 1;
116     for(i = 1,unable = 0;i <= M;i ++)
117     {
118         if(arrive[i] == 0)    unable ++;
119     }
120     printf("0\n%d\n",unable);
121     fclose(stdout);
122     exit(0);
123 }
124
125 int cmp(const void *a,const void *b)
126 {
127     return (((segment *)a)->l - ((segment *)b)->l);
128 }
129
130 int main()
131 {
132     scanf("%d%d",&N,&M);
133     long i,j;
134     for(i = 1;i <= N;i ++)
135         for(j = 1;j <= M;j ++)
136             scanf("%ld",&h[i][j]);
137     for(i = 0;i <= N + 1;i ++)
138         h[i][0] = h[i][M + 1] = LONG_MAX;
139     for(j = 0;j <= M + 1;j ++)
140         h[0][j] = h[N + 1][j] = LONG_MAX;
141     for(i = 1;i <= M;i ++)
142     {
143         memset(arrive,0,sizeof(arrive));
144         range[i] = flow(i);
145     }
146     qsort(range + 1,M,sizeof(segment),cmp);
147     j = 1;
148     int use = 0;
149     int max = 0;
150     for(i = 1;i <= M;)
151     {
152         for(;j <= M;j ++)
153         {
154             if(range[j].l > i)    break;
155             else if(range[j].r > max)
156                 max = range[j].r;
157         }
158         i = max + 1;
159         use ++;
160         if(use > M)  //无法到达所有城市的情况
161         {
162             count();
163         }
164     }
165     printf("1\n%d\n",use);
166     return 0;
167 }

经同学指点，一开始可以把所有第一行的点入队，然后BFS，最后检查最后一行的的点是否都可达即可，这种BFS可以避免许多重复计算，可以节省大量时间。

代码：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <limits.h>
004 #include <string.h>
005 #define MXN 510
006 #define LENGTH 600000
007
008 int di[4] = {0,1,0,-1};
009 int dj[4] = {-1,0,1,0};
010
011 typedef struct point
012 {
013     int i,j;
014 }point;
015
016 typedef struct segment
017 {
018     int l,r;
019 }segment;
020
021 int arrive[MXN];
022 int visit[MXN][MXN];
023 long h[MXN][MXN];
024 segment range[MXN];
025 point queue[LENGTH + 1];
026 int far[MXN] = {};
027 long head,tail;
028
029 int M,N;
030
031 void enqueue(point p)
032 {
033     queue[tail] = p;
034     tail = (tail + 1) % LENGTH;
035 }
036
037 point dequeue()
038 {
039     point r = queue[head];
040     head = (head + 1) % LENGTH;
041     return r;
042 }
043
044 segment flow(int p)  //计算第一行每个点可达的最后一行点的区间
045 {
046     int k;
047     point now,next;
048     now.i = 1;
049     now.j = p;
050     head = tail = 0;
051     enqueue(now);
052     while(head < tail)
053     {
054         now = dequeue();
055         if(now.i == N)
056         {
057             arrive[now.j] = 1;
058         }
059         for(k = 0;k < 4;k ++)
060         {
061             if(h[now.i + di[k]][now.j + dj[k]] < h[now.i][now.j])
062             {
063                 next.i = now.i + di[k];
064                 next.j = now.j + dj[k];
065                 enqueue(next);
066             }
067         }
068     }
069     segment r;
070     for(r.l = 0;r.l <= M && arrive[r.l] == 0;r.l ++);
071     for(r.r = r.l;r.r <= M && arrive[r.r] == 1;r.r ++);
072     r.r -= 1;
073     if(r.r < r.l)    r.r = r.l = 0;
074     return r;
075 }
076
077 void mark(int p)
078 {
079     int k;
080     point now,next;
081     now.i = 1;
082     now.j = p;
083     head = tail = 0;
084     enqueue(now);
085     while(head < tail)
086     {
087         now = dequeue();
088         if(now.i == N)
089         {
090             printf("%d\n",now.j);
091             arrive[now.j] = 1;
092         }
093         for(k = 0;k < 4;k ++)
094         {
095             if(h[now.i + di[k]][now.j + dj[k]] < h[now.i][now.j])
096             {
097                 next.i = now.i + di[k];
098                 next.j = now.j + dj[k];
099                 enqueue(next);
100             }
101         }
102     }
103 }
104
105 void check()  //检查是否全部可达
106 {
107     int i,k;
108     int unable = 0;
109     memset(visit,0,sizeof(visit));  //判重数组初始化
110     point now,next;
111     now.i = 1;
112     head = tail = 0;
113     for(i = 1;i <= M;i ++)
114     {
115         now.j = i;
116         enqueue(now);  //全部入队
117         visit[1][i] = 1;
118     }
119     while(head < tail)
120     {
121         now = dequeue();
122         if(now.i == N)
123         {
124             arrive[now.j] = 1;
125         }
126         for(k = 0;k < 4;k ++)
127         {
128             if(h[now.i + di[k]][now.j + dj[k]] < h[now.i][now.j] && visit[now.i + di[k]][now.j + dj[k]] == 0)
129             {
130                 next.i = now.i + di[k];
131                 next.j = now.j + dj[k];
132                 visit[next.i][next.j] = 1;
133                 enqueue(next);
134             }
135         }
136     }
137     unable = 0;
138     for(i = 1;i <= M;i ++)  //统计不可达节点数
139         if(visit[N][i] == 0)    unable ++;
140     if(unable > 0)
141     {
142         printf("0\n%d\n",unable);
143         fclose(stdout);
144         exit(0);
145     }
146 }
147
148 int cmp(const void *a,const void *b)
149 {
150     return (((segment *)a)->l - ((segment *)b)->l);
151 }
152
153 int main()
154 {
155     scanf("%d%d",&N,&M);
156     long i,j;
157     for(i = 1;i <= N;i ++)
158         for(j = 1;j <= M;j ++)
159             scanf("%ld",&h[i][j]);
160     for(i = 0;i <= N + 1;i ++)
161         h[i][0] = h[i][M + 1] = LONG_MAX;
162     for(j = 0;j <= M + 1;j ++)
163         h[0][j] = h[N + 1][j] = LONG_MAX;
164     check();
165     for(i = 1;i <= M;i ++)
166     {
167         memset(arrive,0,sizeof(arrive));
168         range[i] = flow(i);
169     }
170     //贪心线段覆盖
171     qsort(range + 1,M,sizeof(segment),cmp);
172     j = 1;
173     int use = 0;
174     int max = 0;
175     for(i = 1;i <= M;)
176     {
177         for(;j <= M;j ++)
178         {
179             if(range[j].l > i)    break;
180             else if(range[j].r > max)
181                 max = range[j].r;
182         }
183         i = max + 1;
184         use ++;
185     }
186     printf("1\n%d\n",use);
187     return 0;
188 }