题目链接
大家的 Blog 里面都是做过的题目，只有我的里面什么都没有
那我也开始写一点吧
刷着刷着 DP 不知怎的就出来一道这个题……用时 2 hours 后怒而删两个文件重构……
然后过了……过了……
至今不知道前两遍错在哪里……
Code – first time：连通块染色 +建图，然后二分，广搜判断
Code – second time：连通块染色 +建图，并查集维护连通块大小，做伪 Kruskal
Code – third time：二分，广搜判断
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = + ;
const int maxk = * + ;
int n, h[maxn][maxn], vis[maxn][maxn], flag;
int f[][] = { , , , , -, , , - }; inline int Abs(int x) { return x > ? x : -x; } inline bool Breath_fs(int sx, int sy, int c) {
queue<pair<int, int> > q;
q.push(make_pair(sx, sy)), vis[sx][sy] = ;
int cnt = ;
while( !q.empty() ) {
int x = q.front().first, y = q.front().second;
for(int i = ; i < ; ++i) {
int tx = x + f[i][], ty = y + f[i][];
if( tx < || tx > n || ty < || ty > n ) continue;
if( Abs(h[x][y] - h[tx][ty]) > c || vis[tx][ty] ) continue;
++cnt, vis[tx][ty] = , q.push(make_pair(tx, ty));
}
q.pop();
}
return cnt + > ((n * n) >> ) + ((n * n) & );
} inline bool Check(int x) {
memset(vis, , sizeof vis), flag = ;
for(int i = ; i <= n; ++i) {
for(int j = ; (!flag && j <= n); ++j)
if( !vis[i][j] ) flag = flag | Breath_fs(i, j, x);
if( flag ) break;
}
return flag;
} int main(int argc, char const *argv[])
{
freopen("nanjolno.in", "r", stdin);
freopen("nanjolno.out", "w", stdout); scanf("%d", &n);
for(int i = ; i <= n; ++i) for(int j = ; j <= n; ++j) scanf("%d", &h[i][j]);
int lef = , righ = , mid = (lef + righ) >> , ans = ;
for( ; lef <= righ; mid = (lef + righ) >> )
Check(mid) ? ans = mid, righ = mid - : lef = mid + ;
printf("%d\n", ans); fclose(stdin), fclose(stdout);
return ;
}
—— 晨意微寒秋渐深，侧畔无事俏佳人。
