L2-2 巴音布鲁克永远的土（二分+并查集）

思路：我们可以二分答案，然后判断当前答案合不合理。

对于判断答案合理，可以用并查集，看mid能否把所有检查点连进一个集合中，枚举每个结点，如何当前结点周围的四个方向可以连的话，就加进同一个集合，最后判断所有检查点是否是同一个祖先即可。

代码：

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;
const int N = 1010;
int n, m;
int a[N][N], f[N * N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
vector<int>jc;
int id(int i, int j){return i * m + j;
}int find(int x){if(x != f[x])f[x] = find(f[x]);return f[x];
}bool check(int mid){for(int i = 0;i < n * m;i ++)f[i] = i;for(int i = 0;i < n; i++){for(int j = 0;j < m;j ++){for(int k = 0;k < 4;k ++){int x = i + dx[k], y = j + dy[k];if(x < 0 || y < 0 || x > n || y > m)continue;if(abs(a[x][y] - a[i][j]) <= mid){f[find(id(i, j))] = find(id(x, y));}}}}for(int i = 1;i < jc.size();i ++){if(find(jc[i]) != find(jc[i - 1]))return false;}return true;
}void solve(){cin >> n >> m;for(int i = 0;i < n;i ++){for(int j = 0;j < m;j ++){cin >> a[i][j];}}for(int i = 0;i < n;i ++){for(int j = 0;j < m;j ++){int x;cin >> x;if(x)jc.push_back(id(i, j));}}int l = 0, r = 1e9 + 10;while(l + 1 != r){int mid = l + r >> 1;if(check(mid))r = mid;elsel = mid;}cout << r;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while(t--){solve();}return 0;
}