http://acm.pku.edu.cn/JudgeOnline/problem?id=2922这题是说给个方阵，让你从左上角出发，通过经过相邻的点（上下左右四个方向），到达右下角，要求你经过的路径上的数值的最大值最小值之差最小。
这道题我一开始是枚举最小值O(n)，然后二分最大值与最小值之差O(lgn)，最后去搜索一遍O(n^2)，一个O(n^3 * lgn)的算法，因为n的规模为100，而时限为5000ms，算法可行。跑了2700msAC了。
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 using namespace std;
6
7 const int MAX_N = 110;
8 const int INF = 1000000000;
9 const int dx[] = {0, 0, 1, -1};
10 const int dy[] = {1, -1, 0, 0};
11
12 int a[MAX_N][MAX_N];
13 bool v[MAX_N][MAX_N];
14 int b[MAX_N * MAX_N];
15 int mini, maxi, left, right, mid, ret, tmp;
16 int cas, n, m;
17
18 bool DFS(int i, int j, int l, int h) {
19 if (i == n && j == n) return 1;
20 bool ok = 0;
21 for (int k = 0; k < 4; ++k) {
22 int x = i + dx[k], y = j + dy[k];
23 if (!v[x][y] && a[x][y] >= l && a[x][y] <= h) {
24 v[x][y] = 1;
25 ok = ok | DFS(x, y, l, h);
26 }
27 }
28 return ok;
29 }
30
31 int main() {
32 scanf("%d", &cas);
33 for (int cc = 1; cc <= cas; ++cc) {
34 scanf("%d", &n);
35 for (int i = 0; i <= n + 1; ++i) a[i][0] = a[i][n + 1] = INF;
36 for (int i = 0; i <= n + 1; ++i) a[0][i] = a[n + 1][i] = INF;
37 mini = maxi = a[1][1];
38 for (int i = 1; i <= n; ++i)
39 for (int j = 1; j <= n; ++j) {
40 scanf("%d", &a[i][j]);
41 b[(i - 1) * n + j - 1] = a[i][j];
42 mini = min(mini, a[i][j]);
43 maxi = max(maxi, a[i][j]);
44 }
45 sort(b, b + n * n);
46 int m = unique(b, b + n * n) - b;
47 ret = INF;
48 for (int i = 0; i < m && b[i] <= a[1][1]; ++i) {
49 left = b[i]; right = maxi; tmp = INF;
50 while (left <= right) {
51 mid = (left + right) >> 1;
52 memset(v, 0, sizeof(v));
53 v[1][1] = 1;
54 if (mid >= a[1][1] && DFS(1, 1, b[i], mid)) {
55 tmp = mid - b[i];
56 right = mid - 1;
57 } else {
58 left = mid + 1;
59 }
60 }
61 ret = min(ret, tmp);
62 }
63 printf("Scenario #%d:\n", cc);
64 printf("%d\n\n", ret);
65 }
66 return 0;
67 }
68
AC后看了排名，发现第一名只用了100+ms，那肯定有更好的时间复杂度了。
后来还是枚举最小值，然后逐步放宽最大值与最小值的差，看a[1][1]和a[n][n]是否连通，判是否连通，实际上就是若干个不相交集的并集操作，于是采用了并查集，枚举用了O(n)，每次判连通是O(n^2)，并查集是O(1)的，所以总时间复杂度是O(n^3)。
1900+ms AC了
1 #include <cstdio>
2 #include <cstring>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 const int MAX_N = 110;
9 const int MAX_H = 201;
10 const int dx[] = {0, 0, 1, -1};
11 const int dy[] = {1, -1, 0, 0};
12
13 int a[MAX_N][MAX_N];
14 vector <pair<int, int> > b[MAX_H];
15 int c[MAX_N * MAX_N];
16 int r[MAX_N * MAX_N];
17 int v[MAX_N][MAX_N];
18 int cas, n, m, t, ret;
19
20 int root(int x) {
21 if (x != r[x]) r[x] = root(r[x]);
22 return r[x];
23 }
24
25 void merge(int a, int b) {
26 r[root(a)] = root(b);
27 }
28
29 int main() {
30 scanf("%d", &cas);
31 for (int cc = 1; cc <= cas; ++cc) {
32 scanf("%d", &n);
33 for (int i = 0; i < MAX_H; ++i) b[i].clear();
34 int mini = MAX_H, maxi = 0;
35 for (int i = 1; i <= n; ++i) {
36 for (int j = 1; j <= n; ++j) {
37 scanf("%d", &a[i][j]);
38 b[a[i][j]].push_back(make_pair(i, j));
39 c[(i - 1) * n + j - 1] = a[i][j];
40 mini = min(mini, a[i][j]);
41 maxi = max(maxi, a[i][j]);
42 }
43 }
44 sort(c, c + n * n);
45 m = unique(c, c + n * n) - c;
46 m = lower_bound(c, c + m, min(a[1][1], a[n][n])) - c;
47 memset(v, -1, sizeof(v));
48 ret = MAX_H; t = max(a[1][1], a[n][n]);
49 for (int i = 0; i <= m; ++i) {
50 for (int j = 0; j < n * n; ++j) r[j] = j;
51 for (int j = c[i]; j < t; ++j)
52 for (int k = 0; k < b[j].size(); ++k) {
53 v[b[j][k].first][b[j][k].second] = i;
54 for (int d = 0; d < 4; ++d) {
55 int x = b[j][k].first + dx[d];
56 int y = b[j][k].second + dy[d];
57 if (v[x][y] == i && root((x - 1) * n + y - 1) != root((b[j][k].first - 1) * n + b[j][k].second - 1)) {
58 merge((b[j][k].first - 1) * n + b[j][k].second - 1, (x - 1) * n + y - 1);
59 }
60 }
61 }
62 for (int j = t; j <= maxi; ++j) {
63 for (int k = 0; k < b[j].size(); ++k) {
64 v[b[j][k].first][b[j][k].second] = i;
65 for (int d = 0; d < 4; ++d) {
66 int x = b[j][k].first + dx[d];
67 int y = b[j][k].second + dy[d];
68 if (v[x][y] == i && root((x - 1) * n + y - 1) != root((b[j][k].first - 1) * n + b[j][k].second - 1)) {
69 merge((b[j][k].first - 1) * n + b[j][k].second - 1, (x - 1) * n + y - 1);
70 }
71 }
72 }
73 if (root(0) == root(n * n - 1)) {
74 ret = min(ret, j - c[i]);
75 break;
76 }
77 }
78 }
79 printf("Scenario #%d:\n", cc);
80 printf("%d\n\n", ret);
81 }
82 return 0;
83 }
84