题目链接

  本题是2010年icpc亚洲区域赛杭州赛区的I题

题意

  在一个 n 行 m 列（n≤100，m≤10 000）的网格中有一些探照灯，每个探照灯有一个最大亮度 k（代表这个探照灯可以开到亮度 k, k-1, k-2, …, 1）。如果把一个探照灯开到亮度 L，它可以照亮上下左右各 L 个格子（L=1 表示它只能照亮它自己所在的格子）。下图示是一个开到亮度为3 的探照灯。

  你的任务是选择一些探照灯，把它们开到一个相同的亮度，使得所有格子被监控。为了节约能量，这个相同的亮度应尽量小。一个格子被监控的条件是：要么这个格子本身有一个开着的探照灯，要么这个格子同时被水平方向和垂直方向的探照灯照亮。

输入格式

  输入包含多组数据。每组数据第一行为两个整数 n 和 m，接下来 n 行每行 m 个整数描述各个网格处探照灯的最大亮度 $a_{i,j}$（数值可以为0，表示此网格无探照灯，$a_{i,j}\le 10000$）。最后一行两个 0 表示输入结束。

输出格式

  每组数据输出一行，如果存在满足条件的最小亮度则输出答案，否则输出“NO ANSWER!”。

分析

  比较难的区间覆盖问题，上加权并查集，水平方向和垂直方向分开考虑。

  首先可以想到把数值为 0 的相邻元素合并到一个区间，那么要覆盖此区间就只能在其两侧之外安排探照灯。如果区间两端都到达网格边界，则必然无解；如果仅一端到达网格边界，则可以在其另一端安排探照灯覆盖，探照灯亮度至少为区间长度 L 再加上 1（进而，如果另一端邻近的元素值 ≤ L，则无法保证覆盖，因此也需要将其合并进来）；如果两端均未到达网格边界，则可以在其两端均安排探照灯覆盖，且两侧的探照灯亮度都至少为区间长度 L 的一半向上取整 $\lceil \frac{L}{2}\rceil$。同样地，两侧都可安排探照灯时，探照灯亮度 < $\lceil \frac{L}{2}\rceil$ 的侧边也需要合并进来。以此类推，算法框架就出来了。

1. 把所有元素从小到大排序，初始化每个元素为水平方向及垂直方向的并查集（权值均为 1 ）、当前结果 v = 0 和答案 cc = 0。
2. 遍历那些数值为 cc 的元素并将其合并进原始位置与之相邻且数值 ≤cc 的元素所在集合中，权值 w 为并查集的元素总数。遍历的过程中顺便判定是否无解和更新当前结果 v：
   • 当前元素所在水平方向集合权值达到 m 或者当前元素所在垂直方向集合权值达到 n 则无解（因为对应区间两侧都到边界了，没机会再安排探照灯覆盖了），算法结束。
   • 当前元素所在集合对应区间已经有一侧到边界，另一侧有机会安排探照灯覆盖，更新 $v=max(v,w)$。
   • 当前元素所在集合对应区间两侧都没到边界，两侧都有机会安排探照灯覆盖，更新 $v=max(v,\lceil \frac{w}{2}\rceil )$。
3. 那些数值为 cc 的元素都遍历到后，cc 自增 1：
   • 若 cc > v 则找到答案，算法结束。
   • 否则回到步骤 2。

AC 代码

#include <iostream>
#include <algorithm>
using namespace std;#define M 10010
#define N 102
struct node {int a, x, y;} p[M*N]; int a[N][M], fx[M][N], fy[N][M], sx[M][N], sy[N][M], m, n, s;bool cmp(const node& u, const node& v) {return u.a < v.a;
}int find(int* f, int x) {return x == f[x] ? x : f[x] = find(f, f[x]);
}void merge(int* f, int* s, int x, int y) {int u = find(f, x), v = find(f, y);if (u == v) return;s[u] += s[v]; f[v] = u;
}void solve() {for (int i=s=0; i<n; ++i) for (int j=0; j<m; ++j)cin >> a[i][j], p[s++] = {a[i][j], i, j}, fx[j][i] = i, fy[i][j] = j, sx[j][i] = sy[i][j] = 1;sort(p, p+s, cmp);int c = 0;for (int i=0, cc=0; ; ++cc) {if (cc > c) {cout << cc << endl;return;}for (; i < s && p[i].a == cc; ++i) {int x = p[i].x, y = p[i].y;if (x > 0 && a[x-1][y] <= cc) merge(fx[y], sx[y], x, x-1);if (x+1 < n && a[x+1][y] < cc) merge(fx[y], sx[y], x, x+1);if (y > 0 && a[x][y-1] <= cc) merge(fy[x], sy[x], y, y-1);if (y+1 < m && a[x][y+1] < cc) merge(fy[x], sy[x], y, y+1);int u = find(fx[y], x), v = find(fy[x], y);if (sx[y][u] == n || sy[x][v] == m) {cout << "NO ANSWER!" << endl;return;}c = max(c, find(fx[y], 0) == u || find(fx[y], n-1) == u ? sx[y][u] : (sx[y][u]+1) >> 1);c = max(c, find(fy[x], 0) == v || find(fy[x], m-1) == v ? sy[x][v] : (sy[x][v]+1) >> 1);}}
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m && n) solve();return 0;
}