首页 > 代码库 > [POI2007]POW-The Flood

[POI2007]POW-The Flood

2024-11-02 23:16:39   207人阅读

题目描述

给定一张地势图，所有的点都被水淹没，现在有一些关键点，要求放最少的水泵使所有关键点的水都被抽干

输入输出格式

输入格式：

In the first line of the standard input there are two integers 技术分享 and 技术分享, separated by a single space,技术分享. The following 技术分享 lines contain the description of the map. The 技术分享‘th linedescribes the 技术分享‘th row ofunitary squares in the map. It contains 技术分享 integers 技术分享, separated by single spaces,技术分享, 技术分享.

The number 技术分享 describes the 技术分享‘th square of the ![](http://main.edu.pl/images/OI14/pow-en-tex.14.pn…

输出格式：

Your programme should write out one integer to the standard output - the minimum number of pumpsneeded to drain Byteburg.

输入输出样例

输入样例#1：
6 9
-2 -2 -1 -1 -2 -2 -2 -12 -3
-2 1 -1 2 -8 -12 2 -12 -12
-5 3 1 1 -12 4 -6 2 -2
-5 -2 -2 2 -12 -3 4 -3 -1
-5 -6 -2 2 -12 5 6 2 -1
-4 -8 -8 -10 -12 -8 -6 -6 -4
输出样例#1：
2
我们首先考虑如果在格子 a 修建一个抽水机，在什么情况下格子 b 的水也可以被抽干。
我们可以发现当且仅当存在一条从 a 到 b 的路径，中间经过的抽水机（包括 a）的高度都不大于 b 的高度。
即h[b]>=max(h[i])
因此我们可以考虑把所有格子的高度从小到大排序，我们把每一个格子建成一个集合。
然后按照海拔高度从小到大扫描格子，对于当前的格子 i，我们找到所有与 i 相邻并且海拔高度不大于格子 i 的格子，
我们发现如果这些格子中的任意一个洪水要是被解决了，那么格子 i 的洪水也可以被解决，所以我们合并这些格子。
对于当前的格子 i，如果它必须被清理且与它相邻的格子集合中没有任何一个被清理，我们则把这个集合的清理状态标记为真，然后答案加 1。
集合和每个格子是否被清理用并查集来维护就可以了。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int s,x,y;
 9 } city[1000001],maze[100001];
10 pair<int,int> set[1001][1001];
11 int dx[5]={0,1,-1,0,0};
12 int dy[5]={0,0,0,1,-1};
13 int n,m,a[1001][1001],tot,cnt,vis[1001][1001],ans;
14 bool cmp(node a,node b)
15 {
16     return (a.s<b.s);
17 }
18 pair<int,int> find(pair<int,int> x)
19 {
20     if (set[x.first][x.second]!=x) set[x.first][x.second]=find(set[x.first][x.second]);
21     return set[x.first][x.second];
22 }
23 void union_set(pair<int,int> x,pair<int,int> y)
24 {
25     x=find(x),y=find(y);
26         set[x.first][x.second]=y;
27         vis[y.first][y.second]|=vis[x.first][x.second];
28 }
29 void exam(int x,int y)
30 {
31     for(int i=1;i<=4;i++)
32     {
33         int tx=x+dx[i], ty=y+dy[i];
34         if(tx<=0||ty<=0||tx>m||ty>n) continue;
35         if(a[tx][ty]>a[x][y]) continue;
36         union_set(make_pair(x, y), make_pair(tx, ty));
37     }
38 }
39 int main()
40 {
41     int i,j;
42     cin>>n>>m;
43     for (i=1; i<=n; i++)
44     {
45         for (j=1; j<=m; j++)
46         {
47             scanf("%d",&a[i][j]);
48             if (a[i][j]<=0)
49             {
50                 a[i][j]=-a[i][j];
51             }
52             else
53             {
54                 city[++tot]=(node){a[i][j],i,j};
55             }
56             maze[++cnt]=(node){a[i][j],i,j};
57             set[i][j]=make_pair(i,j);
58         }
59     }
60     sort(maze+1,maze+cnt+1,cmp);
61     sort(city+1,city+tot+1,cmp);
62     for (i=1; i<=tot; i++)
63     {
64         for (j=1; j<=cnt,city[i].s>=maze[j].s; j++)
65         {
66             exam(maze[j].x,maze[j].y);
67             pair<int,int> x=find(make_pair(city[i].x,city[i].y));
68             if (vis[x.first][x.second]==0)
69             {
70                 ans++;
71                 vis[x.first][x.second]=1;
72             }
73         }
74     }
75     cout<<ans;
76 }

 

[POI2007]POW-The Flood


联系
我们