首页 > 代码库 > [NOIP2010]引水入城
[NOIP2010]引水入城
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。
为了使居民们都尽可能饮用 到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因 此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前 提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。
由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。
【输入】
输入文件名为flow.in。输入文件的每行中两个数之间用一个空格隔开。
输入的第一行是两个正整数N和M，表示矩形的规模。
接下来N行，每行M个正整数，依次代表每座城市的海拔高度。
【输出】
输出文件名为flow.out。
输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。
【输入输出样例1】
flow.in
2 5
9 1 5 4 3
8 7 6 1 2
flow.out
1
1
【样例1说明】
只需要在海拔为9的那座城市中建造蓄水厂，即可满足要求。
【输入输出样例2】
flow.in
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
flow.out
1
3
【样例2说明】
湖泊
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
沙漠
上图中，在3个粗线框出的城市中建造蓄水厂，可以满足要求。以这3个蓄水厂为源头在干旱区中建造的输水站分别用3种颜色标出。当然，建造方法可能不唯一。
【数据范围】
本题共有10个测试数据，每个数据的范围如下表所示：
测试数据编号能否满足要求N M
1不能 N≤10 M ≤ 10
2不能 N≤100M≤ 100
3不能 N≤500 M≤ 500
4能 N= 1 M≤ 10
5能 N≤10 M ≤ 10
6能 N≤100 M≤ 20
7能 N≤100 M≤ 50
8能 N≤100 M≤100
9能 N≤200 M≤ 200
10能N≤500 M≤ 500
对于所有的10个数据，每座城市的海拔高度都不超过10^6。
【分析】
又被细节卡了很长时间……不过最后的51ms看起来还是挺爽的2333333
思路是先dp预处理出河边的每个格子的水可以在沙漠边形成的有水的线段，然后贪心做线段覆盖即可。
这里用到了一个结论：如果存在一组解，那么每个河边城市形成的区间必然连续。证明思路：如果某河边城市形成的区间不连续，则“无水”区域边缘内部的任何一个位置都不比外部的节点低，即这一区域外部的水不可能流到内部；而河边城市必然处在区域外部，即其余任意一个河边城市储蓄的水都不可能流入这一区域，这时必然不存在可行解。这样就证明了原命题的逆否命题。于是就无脑记忆化搜索 + 贪心线段覆盖即可。
总时间复杂度为O(m·n + m·log m)，这样看来题目给出的数据范围似乎显得太弱了点。。。。
2 #include <iostream>
3 #include <algorithm>
4 #include <cmath>
5 #include <cctype>
6 #include <queue>
7 using namespace std;
8 #if defined DEBUG
9 FILE *in = fopen("test","r");
10 #define out stdout
11 #else
12 FILE *in = fopen("flow.in","r");
13 FILE *out = fopen("flow.out","w");
14 #endif
15 inline void getint(int &x){
16 int c = fgetc(in);
17 while(!isdigit(c))c = fgetc(in);
18 x = c - ‘0‘;
19 while(isdigit(c = fgetc(in)))x = x * 10 - ‘0‘ + c;
20 }
21 /*==================================================*/
22 const int maxn = 500 + 2;
23 typedef pair<int, int> RNG;//Range
24 inline bool cmp(const RNG &a, const RNG &b){
25 if(!(a.first | a.second))return 0;
26 if(!(b.first | b.second))return 1;
27 if(a.first == b.first)return a.second > b.second;
28 return a.first < b.first;
29 }
30 inline RNG operator + (const RNG &a, const RNG &b){//Union
31 RNG x, y;
32 int l, r;
33 if(cmp(b, a))x = b, y = a;
34 else x = a, y = b;
35 if(!(y.first | y.second))return x;
36 l = x.first, r = max(x.second, y.second);
37 return RNG(l, r);
38 }
39 RNG rng[maxn][maxn]; //‘Wet‘ Ranges (caused by water in G[i][j])
40 int N, M, G[maxn][maxn];
41 bool known[maxn][maxn] = {0}, wet[maxn] = {0};
42 inline void dfs(int x, int y){ //Dynamic Programming
43 RNG ans = RNG(0, 0);
44 if(x == N-1)wet[y] = 1, ans = RNG(y, y+1);
45 if(x && G[x-1][y] < G[x][y]){
46 if(!known[x-1][y])dfs(x-1, y);
47 ans = ans + rng[x-1][y];
48 }
49 if(y && G[x][y-1] < G[x][y]){
50 if(!known[x][y-1])dfs(x, y-1);
51 ans = ans + rng[x][y-1];
52 }
53 if(x < N-1 && G[x+1][y] < G[x][y]){
54 if(!known[x+1][y])dfs(x+1, y);
55 ans = ans + rng[x+1][y];
56 }
57 if(y < M-1 && G[x][y+1] < G[x][y]){
58 if(!known[x][y+1])dfs(x, y+1);
59 ans = ans + rng[x][y+1];
60 }
61 known[x][y] = 1;
62 rng[x][y] = ans;
63 }
64 inline int cover(){ //Greedy Algorithm - Line Coverage
65 sort(rng[0], rng[0] + M, cmp);
66 int ans = 1, curr, maxr, i;
67 curr = rng[0][0].second;
68 for(i = 1;i < M && (rng[0][i].first | rng[0][i].second);){
69 maxr = curr;
70 while((rng[0][i].first|rng[0][i].second)&&rng[0][i].first <= curr){
71 if(rng[0][i].second > maxr)maxr = rng[0][i].second;
72 ++i;
73 }
74 if(maxr > curr)++ans, curr = maxr;
75 }
76 return ans;
77 }
78 inline void work(){
79 getint(N), getint(M);
80 int i, j, dry = 0;
81 for(i = 0;i < N;++i)for(j = 0;j < M;++j)
82 getint(G[i][j]);
83 for(j = 0;j < M;++j)
84 dfs(0, j);
85 for(j = 0;j < M;++j)
86 if(!wet[j])++dry;
87 if(dry) fprintf(out, "0\n%d\n", dry);
88 else fprintf(out, "1\n%d\n", cover());
89 }
90 int main(){
91 work();
92 return 0;
93 }
[NOIP2010]引水入城