自动搬运

查看原文

来自洛谷，原作者为

	Find_Yourself 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 22:28:04，当前版本为作者最后更新于2022-09-24 17:20:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

通过观察，可以发现此题和最小生成树十分相似（两个地点之间途经的最小值最大）。

于是可以考虑这么做：

1. 通过 bfs 将每一个块预处理出来，并记录其编号、高度、类型（是否为高地）以及边缘的点。

2. 将每一个块按高度从大到小排序。

3. 依次枚举每个块：

   • 对于当前要处理的块，枚举其边界的所有点，看会与哪些已插入的块相连，同时用并查集找到他们的“祖先”，即该块所连接形成的连通块内最高的高地。然后除了最高的“祖先”，其他高地途经的最小值最大为当前块的高度。

   • 将这些集合合并，更新其“祖先”。

4. 排序并输出答案。

要注意的是，由于每个集合内最高的高地可能有多个，所以需要开个数组记录一下。

具体看代码吧。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5, N2 = 1e5 + 5;
int n, m, a[N][N], id[N][N], fa[N2], vis[N2], dd[N2], dx[] = {0, 0, -1, 1, -1, -1, 1, 1}, dy[] = {-1, 1, 0, 0, -1, 1, 1, -1}, num[N2], tot = 0;
struct node{int id, h, type; vector<int> v;}b[N2]; //块 
struct node2{int i, j; node2(int i = 0, int j = 0):i(i), j(j){}};
struct node3{int h, minn;}ans[N2];
bool cmp(node x, node y) {return x.h > y.h;}
bool cmp2(int x, int y) {return b[x].h > b[y].h;}
bool cmp3(node3 x, node3 y) {if (x.h != y.h) return x.h > y.h; return x.minn > y.minn;}
int ff(int x) {return (fa[x] == x)?x:fa[x] = ff(fa[x]);}
queue<node2> q;
vector<int> tmp;
void bfs(int sx, int sy) {
	q.push(node2(sx, sy)); ++tot;
	b[tot].id = tot; b[tot].h = a[sx][sy];
	id[sx][sy] = tot;
	int f1 = 1; //该连通块是否为高地 
	while (!q.empty()) {
		node2 u = q.front(); q.pop();
		int f2 = 0; //该点是否在边缘上 
		for (int k = 0; k <= 7; ++k) {
			int tx = u.i + dx[k], ty = u.j + dy[k];
			if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
			if (a[tx][ty] == a[sx][sy] && !id[tx][ty]) q.push(node2(tx, ty)), id[tx][ty] = tot;
			if (a[tx][ty] != a[u.i][u.j]) f2 = 1;
			if (a[tx][ty] > a[u.i][u.j]) f1 = 0;
		}
		if (f2) b[tot].v.push_back((u.i - 1) * m + u.j); 
	}
	b[tot].type = f1;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> a[i][j];
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (!id[i][j]) bfs(i, j);
		}
	}
	int maxn = 0, cnt = 0;
	sort(b + 1, b + tot + 1, cmp);
	for (int i = 1; i <= tot; ++i) {
		fa[i] = i; dd[b[i].id] = i; maxn = max(maxn, b[i].h);
		num[i] = b[i].type;
	}
	for (int i = 1; i <= tot; ++i) if (b[i].h == maxn) ans[++cnt].h = maxn, ans[cnt].minn = 0; //先将最高的高地的答案处理了 
	for (int t = 1; t <= tot; ++t) {
		vis[t] = 1; //记录每个块是否已插入 
		tmp.clear(); tmp.push_back(t); //tmp记录与当前块相邻的块 
		for (int i = 0; i < b[t].v.size(); ++i) {
			int x = (b[t].v[i] - 1) / m + 1, y = b[t].v[i] % m;
			if (!y) y = m;
			for (int k = 0; k <= 7; ++k) {
				int tx = x + dx[k], ty = y + dy[k];
				if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
				int d = ff(dd[id[tx][ty]]);
				if (vis[d] && d != t) tmp.push_back(d); //记录其下标 
			}
		}
		sort(tmp.begin(), tmp.end());
		tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); //去重 
		sort(tmp.begin(), tmp.end(), cmp2); //将其高度从大到小排序，方便后续处理 
		int fir = tmp[0], c = 0; //fir表示最高的高地 
		for (int i = 0; i < tmp.size(); ++i) {
			if (b[tmp[i]].type && num[tmp[i]]) {
				++c;
				if (c == 1) fir = tmp[i];
				else {
					if (b[tmp[i]].h == b[fir].h) { //高度一样，合并到fir 
						num[fir] += num[tmp[i]];
						num[tmp[i]] = 0;
					} else {
						for (int j = 0; j < num[tmp[i]]; ++j) ans[++cnt].h = b[tmp[i]].h, ans[cnt].minn = b[t].h; //记录答案 
						num[tmp[i]] = 0;
					}
				}
			}
		}
		for (int i = 0; i < tmp.size(); ++i) { //合并集合 
			if (tmp[i] != fir) {
				fa[tmp[i]] = fir;
			}
		}
	}
	sort(ans + 1, ans + cnt + 1, cmp3);
	cout << cnt << endl;
	for (int i = 1; i <= cnt; ++i) cout << ans[i].h << " " << ans[i].minn << endl;
	return 0;
}