杭州网站建设招聘,wordpress安装主题,六安网新闻,设计本质安全题目描述 给定一张地势图#xff0c;所有的点都被水淹没#xff0c;现在有一些关键点#xff0c;要求放最少的水泵使所有关键点的水都被抽干 输入输出格式 输入格式#xff1a; In the first line of the standard input there are two integers and , separated by a sin…题目描述 给定一张地势图所有的点都被水淹没现在有一些关键点要求放最少的水泵使所有关键点的水都被抽干 输入输出格式 输入格式 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 因此我们可以考虑把所有格子的高度从小到大排序我们把每一个格子建成一个集合。然后按照海拔高度从小到大扫描格子对于当前的格子 i我们找到所有与 i 相邻并且海拔高度不大于格子 i 的格子我们发现如果这些格子中的任意一个洪水要是被解决了那么格子 i 的洪水也可以被解决所以我们合并这些格子。对于当前的格子 i如果它必须被清理且与它相邻的格子集合中没有任何一个被清理我们则把这个集合的清理状态标记为真然后答案加 1。集合和每个格子是否被清理用并查集来维护就可以了。 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 using namespace std;6 struct node7 {8 int s,x,y;9 } city[1000001],maze[100001];
10 pairint,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.sb.s);
17 }
18 pairint,int find(pairint,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(pairint,int x,pairint,int y)
24 {
25 xfind(x),yfind(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 i1;i4;i)
32 {
33 int txxdx[i], tyydy[i];
34 if(tx0||ty0||txm||tyn) 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 cinnm;
43 for (i1; in; i)
44 {
45 for (j1; jm; 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(maze1,mazecnt1,cmp);
61 sort(city1,citytot1,cmp);
62 for (i1; itot; i)
63 {
64 for (j1; jcnt,city[i].smaze[j].s; j)
65 {
66 exam(maze[j].x,maze[j].y);
67 pairint,int xfind(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 coutans;
76 } 转载于:https://www.cnblogs.com/Y-E-T-I/p/7221242.html
