题目背景
天道酬勤,婆罗门的科研团队废寝忘食,终于制造出了自己的火箭,然而,火箭发射基地在遥远的地方。现在婆罗门要把这枚火箭运向火箭发射基地,但婆罗门制造火箭之后变得很穷,请你帮忙解决如下问题。
题目描述
婆罗门的地形起伏,要将火箭运到发射基地必须要经过军事基地,这些军事基地构成了 n × m的网格图。
每个基地都有它的***度,相邻基地之间转移的花费是他们的***度之差。火箭运输车从(1, 1)出发,终点为(n, m),
求一条路径,使得路径上的最大花费最小。
输入输出格式
输入格式:
第一行两个整数 n, m。
接下来 n行每行 m个整数,第 i行第 j个数代表位于(i, j)这个军事基地的***度 Wi,j。
输出格式:
输出一个整数,代表答案。
输入输出样例
输入样例#1:
3 3 1 2 3 4 5 6 7 8 9
输出样例#1:
3
说明
对于 30%的数据,n, m ≤ 4.
对于 60%的数据, n, m, Wi,j ≤ 100.
对于 100%的数据, n, m ≤ 1000, 0 ≤ Wi,j ≤ 109 .
主要思路:DP最小生成树
想必大家都做过货车运输吧,当时我们用最小生成树维护最小的最大值。
这里我们可以用同样的思路,把每一个坐标作为一个点,维护一个这样的最小生成树,因为我们只需要求(1,1)到(n,m)的路径中最小的最大花费,所以我们建树时只需要建到(1,1)与(n,m)点在同一子集中即可。
P.S. DP死了?
不存在的。
但是要注意这个时候的DP就只能写记忆化了。因为这个并不是一个简单的二维DP,它可以扩展的方向是4个方向,不是两个QAQ(不会告诉你我考试时就是因为写普通DP式子炸的)
代码实现(Kruscal
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define go(i, j, n, k) for (int i = j; i <= n; i += k) #define fo(i, j, n, k) for (int i = j; i >= n; i -= k) #define rep(i, x) for (int i = h[x]; i; i = e[i].nxt) #define mn 2000010 #define mm 1111 #define inf 1 << 30 #define ll long long #define ld long double #define fi first #define se second #define root 1, n, 1 #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define bson l, r, rt inline int read(){ int f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } inline void write(int x){ if (x < 0)putchar('-'),x = -x; if (x > 9)write(x / 10); putchar(x % 10 + '0'); } //This is AC head above... struct node{ int x, y, w; } e[mn]; int n, m, ans, tot; int N, M; inline bool cmp(node a,node b){ return a.w < b.w; } int f[mn]; inline int findx(int x){ return f[x] == x ? x : f[x] = findx(f[x]); } inline void mergex(int x,int y){ int xx = findx(x); int yy = findx(y); if(xx==yy) return; //srand((unsigned)time(NULL)); if(rand()%2){ f[xx] = yy; }else{ f[yy] = xx; } } int a[mm][mm], num[mm][mm]; inline void Kru(){ go(i,1,N,1){ f[i] = i; } sort(e + 1, e + M + 1, cmp); go(i,1,M,1){ if(findx(e[i].x) != findx(e[i].y)){ mergex(e[i].x, e[i].y); ans = max(ans, e[i].w); if(++tot == N-1){ return; } if(findx(1) == findx(N)) return; } } } inline int abss(int aa) { return aa > 0 ? aa : -aa; } int main(){ //srand((unsigned)time(NULL)); n = read(), m = read(); /* go(i,1,m,1){ e[i].x = read(), e[i].y = read(), e[i].w = read(); }*/ go(i,1,n,1) { go(j,1,m,1) { a[i][j] = read(); num[i][j] = ++N; } } go(i,1,n,1) { go(j,1,m,1) { if(i<n) { e[++M].x=num[i][j], e[M].y = num[i + 1][j], e[M].w = abss(a[i][j] - a[i + 1][j]); } if(j<m) { e[++M].x=num[i][j], e[M].y = num[i][j + 1], e[M].w = abss(a[i][j] - a[i][j + 1]); } } } Kru(); cout << ans; return 0; }