首页 > 代码库 > P1514 引水入城
P1514 引水入城
题目描述
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。
因此，只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。
输入输出格式
输入格式：
输入文件的每行中两个数之间用一个空格隔开。输入的第一行是两个正整数N 和M，表示矩形的规模。接下来N 行，每行M 个正整数，依次代表每座城市的海拔高度。
输出格式：
输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。
输入输出样例
输入样例#1：
【输入样例1】2 59 1 5 4 38 7 6 1 2【输入样例2】3 68 4 5 6 4 47 3 4 3 3 33 2 2 1 1 2
输出样例#1：
【输出样例1】11【输出样例2】13
说明
【样例1 说明】
只需要在海拔为9 的那座城市中建造蓄水厂，即可满足要求。
【样例2 说明】
上图中，在3 个粗线框出的城市中建造蓄水厂，可以满足要求。以这3 个蓄水厂为源头
在干旱区中建造的输水站分别用3 种颜色标出。当然，建造方法可能不唯一。
【数据范围】
DFS+线段覆盖
注意不知道为什么需要先跑一边DFS求是否能完全覆盖
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 const int MAXN=1001; 9 void read(int & n) 10 { 11 char c=‘+‘;int x=0;bool flag=0; 12 while(c<‘0‘||c>‘9‘) 13 {c=getchar();if(c==‘-‘)flag=1;} 14 while(c>=‘0‘&&c<=‘9‘) 15 {x=x*10+(c-48);c=getchar();} 16 flag==1?n=-x:n=x; 17 } 18 int n,m; 19 int map[MAXN][MAXN]; 20 struct node 21 { 22 int l,r,id; 23 }xushui[MAXN]; 24 int xx[5]={-1,+1,0,0}; 25 int yy[5]={0,0,-1,+1}; 26 int vis[MAXN]; 27 int vis2[MAXN][MAXN]; 28 int happen=0; 29 void pdcan(int x,int y) 30 { 31 if(x==n) 32 happen++; 33 vis2[x][y]=1; 34 for(int i=0;i<4;i++) 35 { 36 int wx=x+xx[i]; 37 int wy=y+yy[i]; 38 if(vis2[wx][wy]==0&&map[wx][wy]<map[x][y]&&wx>=1&&wy>=1&&wx<=n&&wy<=m) 39 pdcan(wx,wy); 40 } 41 } 42 void dfs(int num,int x,int y) 43 { 44 if(x==n) 45 { 46 xushui[num].l=min(xushui[num].l,y); 47 xushui[num].r=max(xushui[num].r,y); 48 vis[y]=1; 49 } 50 for(int i=0;i<4;i++) 51 { 52 int wx=x+xx[i]; 53 int wy=y+yy[i]; 54 if(map[wx][wy]<map[x][y]&&wx>=1&&wy>=1&&wx<=n&&wy<=m) 55 dfs(num,wx,wy); 56 } 57 } 58 int cannot=0; 59 int comp(const node & a,const node & b) 60 { 61 if(a.l==b.l) 62 return a.r>b.r; 63 return a.l<b.l; 64 } 65 int main() 66 { 67 freopen("flow.in","r",stdin); 68 freopen("flow.out","w",stdout); 69 read(n);read(m); 70 for(int i=1;i<=m;i++) 71 { 72 xushui[i].l=0x7ffff; 73 xushui[i].r=-1; 74 } 75 for(int i=1;i<=n;i++) 76 for(int j=1;j<=m;j++) 77 read(map[i][j]); 78 for(int i=1;i<=m;i++) 79 if(vis2[1][i]==0) 80 pdcan(1,i); 81 if(happen!=m) 82 { 83 printf("0\n%d",m-happen); 84 return 0; 85 } 86 for(int i=1;i<=m;i++) 87 { 88 xushui[i].id=i; 89 dfs(i,1,i); 90 } 91 for(int i=1;i<=m;i++) 92 if(vis[i]==0) 93 cannot++; 94 if(cannot) 95 { 96 printf("0\n%d",cannot); 97 return 0; 98 } 99 int to=0;//已经伸展到的最远长度100 int now=0;101 int ans=0;// 需要几个点 102 for(int i=1;i<=m;i++)103 {104 if(xushui[i].l>1001)continue;105 if(now+1>=xushui[i].l)106 to=max(to,xushui[i].r);107 else 108 {109 now=to;110 to=max(to,xushui[i].r);111 ans++;112 }113 }114 if(now!=m)115 printf("1\n%d",ans+1);116 else117 printf("1\n%d",ans);118 return 0;119 }
P1514 引水入城
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。