Description
The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000. Some of the cells in this grid are designated as starting points for the course. The organizers of the Moolympics want to assign a difficulty rating to each starting point. The difficulty level of a starting point P should be the minimum possible value of D such that a cow can successfully reach at least T total cells of the grid (1 <= T <= MN), if she starts at P and can only move from cell to adjacent cell if the absolute difference in elevation between the cells is at most D. Two cells are adjacent if one is directly north, south, east, or west of the other. Please help the organizers compute the difficulty rating for each starting point.
给定一个n*m的高度矩阵，一个点的难度P是指 最小的D使得以这个点为起点，可到达的格子数量至少为T，一个格子可以到另外一个格子必须保证两个格子相邻且高度差不超过D，相邻是指4-相邻。再给定一个同样大小的01矩阵，求出所有1处格子的难度和。
Line 1: The integers M, N, and T.
Lines 2..1+M: Each of these M lines contains N integer elevations.
Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, with 1 indicating a cell that is a starting point.
Output
- Line 1: The sum of difficulty ratings of all starting points (note that this may not fit into a 32-bit integer, even though individual difficulty ratings will).
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
Sample Output
24
Solution
一开始还以为是整体二分+可持久化并查集。。。
相邻格子连边，边权为高度差。按权值排序后从前往后扫一遍，用并查集维护连通状态、当前联通块内1的数量、当前联通块大小。如果合并之前小于T，当合并操作完成后大于T了，更新一下答案就好辣！
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
const int maxn = 600*600;
int ez[maxn], ey[maxn], ex[maxn];
int f[maxn], siz[maxn], cnt[maxn], eid[maxn];
int n, m, T, H[600][600], id[600][600], tot;
bool cmp(int x, int y) {
return ez[x] < ez[y];
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
n = getint(); m = getint(); T = getint();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
H[i][j] = getint();
id[i][j] = ++tot;
f[tot] = tot;
siz[tot] = 1;
}
tot = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (getint())
cnt[id[i][j]] = 1;
for (int k = 0; k < 2; ++k) {
int tx = i + dx[k], ty = j + dy[k];
if (1 <= tx && tx <= n && 1 <= ty && ty <= m) {
ex[++tot] = id[i][j];
ey[tot] = id[tx][ty];
ez[tot] = abs(H[i][j] - H[tx][ty]);
eid[tot] = tot;
}
}
}
sort(eid+1, eid+tot+1, cmp);
LL ans = 0;
for (int i = 1; i <= tot; ++i) {
int now = eid[i], a = find(ex[now]), b = find(ey[now]);
if (a == b) continue;
if (siz[a] + siz[b] >= T) {
if (siz[a] < T) ans += LL(cnt[a]) * ez[now];
if (siz[b] < T) ans += LL(cnt[b]) * ez[now];
}
if (siz[a] < siz[b])
swap(a, b);
f[b] = a;
siz[a] += siz[b];
cnt[a] += cnt[b];
}
printf("%lld", ans);
return 0;
}
|