noip2010 引水入城 - bfs + 贪心-白红宇

noip2010 引水入城 - bfs + 贪心

阅读量：5213 次

发布时间：2019-06-14

本文共 2719 字，大约阅读时间需要 9 分钟。

题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 $\times M×M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。$

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第

输入输出格式

输入格式：

每行两个数，之间用一个空格隔开。输入的第一行是两个正整数

输出格式：

两行。如果能满足要求，输出的第一行是整数

题解

先对于每一个沿湖城市做一遍bfs，求出从那个城市出发能够到达的沙漠旁的城市的区间，若不是一段区间，则必定不能全部覆盖，做完bfs后可以直接判断。

接着再贪心区间覆盖，求出最少的区间数，即为答案

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define rd read() 6 #define rep(i,a,b) for( int i = (a); i <= (b); ++i ) 7 #define per(i,a,b) for( int i = (a); i >= (b); --i ) 8 using namespace std; 9 typedef pair
          
            P;10 11 queue
           q;12 13 const int N = 505, inf = 1061109567;14 15 int n, m, h[N][N], vis[N][N], ok[N], tot ;16 17 int dx[4] = { 0, 0, -1, 1}, dy[4] = { 1, -1, 0, 0};18 19 struct node {20 int l, r;21 }ln[N];22 23 int read() {24 int X = 0, p = 1; char c = getchar();25 for(; c > '9' || c < '0'; c = getchar() ) if( c == '-' ) p = -1;26 for(; c >= '0' && c <= '9'; c = getchar() ) X = X * 10 + c - '0';27 return X * p;28 }29 30 void bfs( int x ) {31 memset(vis, 0, sizeof(vis));32 q.push( P( 1, x ) );33 vis[1][x] = 1;34 ln[x].l = n + 1, ln[x].r = 0;35 if( n == 1 && !ok[x] ) {36 ok[x] = 1;37 tot++;38 ln[x].l = x;39 ln[x].r = x;40 }41 for( P u, to; !q.empty(); ) {42 u = q.front(); q.pop();43 for( int i = 0; i < 4; ++i ) {44 int nx = u.first + dx[i], ny = u.second + dy[i];45 if( !nx || !ny || nx > n || ny > m || vis[nx][ny]) continue;46 if( h[nx][ny] >= h[u.first][u.second] ) continue;47 vis[nx][ny] = 1;48 if( nx == n ) {49 ln[x].l = min( ln[x].l, ny);50 ln[x].r = max( ln[x].r, ny);51 if( !ok[ny] ) ok[ny] = 1, tot++;52 }53 q.push( P( nx, ny ) );54 }55 }56 }57 58 int cmp( const node &A, const node &B ) {59 return A.l == B.l ? A.r < B.r : A.l < B.l;60 }61 62 int main()63 {64 n = rd, m = rd;65 rep( i, 1, n ) rep( j, 1, m ) h[i][j] = rd;66 rep( i, 1, m ) if( h[1][i] >= h[1][i - 1] && h[1][i] >= h[1][i + 1]) bfs( i );67 if( tot != m ) return printf("0\n%d\n", m - tot), 0;68 sort(ln + 1, ln + 1 + m, cmp);69 int l = 1, r = 1, ans = 0, now = 1;70 for(; r <= m; ) {71 for(; ln[now].l <= r && now <= m; now++ ) l = max( l, ln[now].r );72 ans++;73 r = l + 1;74 }75 printf("1\n%d\n", ans);76 }

View Code

转载于:https://www.cnblogs.com/cychester/p/9467592.html

你可能感兴趣的文章