入城"/>
CODEVS 1066 引水入城
题目描述 Description
在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊,刚好构成一个N行M列的矩形,如上图所示,其中每个格子都代表一座城 市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施 有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的 蓄水池中。因此,只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通 过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是 存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。 由于第N行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利 设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干 旱区中不可能建有水利设施的城市数目。
输入描述 Input Description
输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M,表示矩形的规模。 接下来N行,每行M个正整数,依次代表每座城市的海拔高度。
输出描述 Output Description
输出有两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少 建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有 几座干旱区中的城市不可能建有水利设施。
样例输入 Sample Input
2 5
9 1 5 4 3
8 7 6 1 2
样例输出 Sample Output
1
1
昨天晚上帝江学长安利给我这道题(Orz Loi_Dijiang),说是一道裸的灌水…结果我打的BFS调了好一会….
第一问比较好求,把第一行所有的点扔队列里,然后跑BFS,看最后一行是不是都能到达。
第二问是一个线段覆盖DP?= =,给你一堆小区间,和一个大区间,要求用最少的小区间覆盖整个大区间….
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1000;
const int inf=0x7fffffff;
int map[maxn][maxn];
bool vis[maxn][maxn];
int tmp[maxn];
int n,m;
int xx[]={0,1,0,-1,0};
int yy[]={0,0,1,0,-1};
struct meico
{int x;int y;
};
struct hah
{int l;int r;
}sz[maxn],xd[maxn];queue<meico>q;
bool pd(int x1,int y1)
{if(vis[x1][y1]&&map[q.front().x][q.front().y]>map[x1][y1])return true;return false;
}
int ans=0,ans1=0;
void bfs()
{while(!q.empty()){vis[q.front().x][q.front().y]=0;for(int i=1;i<=4;i++){int x1=q.front().x;int y1=q.front().y;x1+=xx[i];y1+=yy[i];if(pd(x1,y1)){vis[x1][y1]=0;q.push((meico){x1,y1});}}q.pop();}
}
bool cmp(int a,int b)
{return a>b;
}
bool cmp2(hah a,hah b)
{if(a.l!=b.l)return a.l<b.l;elsereturn a.r<b.r;
}
int tot;
void hahah()
{sort(xd+1,xd+tot+1,cmp2);int now=0,ans=0;for(int i=1,to=0;i<=tot;i++){if(now+1>=xd[i].l) to=max(to,xd[i].r);else {now=to,to=max(to,xd[i].r);ans++; }}if(now!=m) ans++;printf("%d",ans);//奇怪的线段覆盖DP
}
void bfs1(int a)
{ for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)vis[i][j]=1;while(!q.empty()){for(int i=1;i<=4;i++){int x1=q.front().x;int y1=q.front().y;if(x1==n){sz[a].l=min(sz[a].l,y1);sz[a].r=max(sz[a].r,y1);}x1+=xx[i];y1+=yy[i];if(pd(x1,y1)){vis[x1][y1]=0;if(x1==n){sz[a].l=min(sz[a].l,y1);sz[a].r=max(sz[a].r,y1);}q.push((meico){x1,y1});}}q.pop();}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&map[i][j]),vis[i][j]=1;for(int i=1;i<=m;i++)tmp[i]=map[1][i];sort(tmp+1,tmp+1+m,cmp);for(int i=1;i<=m;i++){sz[i].l=inf;if(vis[1][i]){q.push((meico){1,i});bfs();}}for(int i=1;i<=m;i++){if(vis[n][i])ans++;}if(ans)printf("0\n%d\n",ans);else{puts("1");for(int i=1;i<=m;i++){q.push((meico){1,i});bfs1(i);}for(int i=1;i<=m;i++){if(sz[i].l!=inf&&sz[i].r!=0){xd[++tot].l=sz[i].l;xd[tot].r=sz[i].r;}}for(int i=1;i<=tot;i++){// printf("i:%d l:%d r:%d\n",i,xd[i].l,xd[i].r);}hahah();}return 0;}
更多推荐
CODEVS 1066 引水入城
发布评论