感觉自己什么题都写不动了。

又是一个神贪心:把所有城市中的点按照高度从小到大排序之后拿出来逐个计算,枚举其他高度小于它的点向四周扩展,如果这个点不能被之前放过的抽水机覆盖,那么把答案加一,并在这个点放上一台抽水机。这个过程适合用并查集来维护。

非常懒的我把地图周围一圈都赋值为无限大。

这样子保证了城市中的所有点能够被最小代价地覆盖。

时间复杂度$O(nm log nm)$,有点卡常。

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = ;
const int dx[] = {, , -, };
const int dy[] = {, , , -};
const int inf = << ; int n, m, tot = , a[N][N], ufs[N * N];
bool vis[N * N]; struct Node {
int x, y, val; friend bool operator < (const Node &u, const Node &v) {
return u.val < v.val;
} } b[N * N], c[N * N]; inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > ''|| ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline int id(int x, int y) {
return (x - ) * m + y;
} int find(int x) {
return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
} inline void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx == fy) return;
ufs[fx] = fy;
if(vis[fx]) vis[fy] = ;
} inline void ext(int x, int y) {
for(int i = ; i < ; i++) {
int tox = x + dx[i], toy = y + dy[i];
if(a[tox][toy] <= a[x][y]) merge(id(tox, toy), id(x, y));
}
} int main() {
read(n), read(m);
for(int i = ; i <= n; i++)
for(int j = ; j <= m; j++) {
read(a[i][j]);
if(a[i][j] > ) c[++tot] = (Node) {i, j, a[i][j]};
else a[i][j] *= -;
b[id(i, j)].x = i, b[id(i, j)].y = j, b[id(i, j)].val = a[i][j];
ufs[id(i, j)] = id(i, j);
} for(int i = ; i <= m + ; i++)
a[][i] = a[n + ][i] = inf;
for(int i = ; i <= n + ; i++)
a[i][] = a[i][m + ] = inf; sort(b + , b + + n * m);
sort(c + , c + + tot); /* for(int i = 1; i <= tot; i++)
printf("%d %d %d\n", c[i].x, c[i].y, c[i].val); */ int ans = ;
for(int j = , i = ; i <= tot; i++) {
for(; j <= n * m && c[i].val >= b[j].val; j++)
ext(b[j].x, b[j].y);
int now = find(id(c[i].x, c[i].y));
if(!vis[now]) {
vis[now] = ;
ans++;
}
} printf("%d\n", ans);
return ;
}

最新文章

  1. js数组方法
  2. T-SQL Recipes之Index Defragmentation
  3. POS管理系统之出入库单分页查询
  4. iOS--页面跳转(UITableView)
  5. 第二课 less的学习以及移动端需要注意的问题
  6. 原生 js 写分页
  7. Unity 3D Intantiate过程中Transform 空物体和本体之间的关系
  8. UML中关系图解
  9. 主运行循环main run loop的一些理解
  10. [翻译] .NET Core 2.1 发布
  11. vue使用babel+sass出错解决
  12. 二层协议--MPLS协议总结
  13. ubuntu 禁用 nouveau 方法
  14. 开发同学的福利--mysql监控工具sqlprofiler,类似sqlserver的profiler工具
  15. mark_save
  16. bzoj 2844 albus就是要第一个出场 - 线性基
  17. FICO年终完全手册
  18. 网络协议理论,http协议,数据结构,常用返回码
  19. PHP用ActiveMq 实现消息列队
  20. http请求状态及其含义表

热门文章

  1. 在ios7中使用zxing
  2. python_Notepad++编码集的说明
  3. Java实现LSH(Locality Sensitive Hash )
  4. 自定义php(NON-CORE WORDPRESS FILE) 引用 wordpress
  5. Linux命令学习(17):ifconfig命令
  6. TCP状态详解
  7. 【Linux网络编程】基于TCP流 I/O多路转接(poll) 的高性能http服务器
  8. java restful response 万能类
  9. [置顶] strcpy()与strncpy()的区别
  10. Ubuntu16.04+TensorFlow r1.12环境搭建指南