題目鏈接

??本題是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 的一半向上取整 $?\frac{L}{2}?$。同樣地，兩側都可安排探照燈時，探照燈亮度 < $?\frac{L}{2}?$ 的側邊也需要合并進來。以此類推，算法框架就出來了。

1. 把所有元素從小到大排序，初始化每個元素為水平方向及垂直方向的并查集（權值均為 1 ）、當前結果 v = 0 和答案 cc = 0。
2. 遍歷那些數值為 cc 的元素并將其合并進原始位置與之相鄰且數值 ≤cc 的元素所在集合中，權值 w 為并查集的元素總數。遍歷的過程中順便判定是否無解和更新當前結果 v：
   • 當前元素所在水平方向集合權值達到 m 或者當前元素所在垂直方向集合權值達到 n 則無解（因為對應區間兩側都到邊界了，沒機會再安排探照燈覆蓋了），算法結束。
   • 當前元素所在集合對應區間已經有一側到邊界，另一側有機會安排探照燈覆蓋，更新 $v=max(v,w)$。
   • 當前元素所在集合對應區間兩側都沒到邊界，兩側都有機會安排探照燈覆蓋，更新 $v=max(v,?\frac{w}{2}?)$。
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;
}