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[] = {001-1};
10 const int dy[] = {1-100};
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, 0sizeof(v));
53                 v[1][1= 1;
54                 if (mid >= a[1][1&& DFS(11, 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[] = {001-1};
11 const int dy[] = {1-100};
12 
13 int a[MAX_N][MAX_N];
14 vector <pair<intint> > 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, -1sizeof(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