题意：有n*m个单位的农田，给定每个单位农田地势高低，现在需要灌溉所有农田，如果把水引入相邻的农田里需要的管道长度为两者的高度差。求最少的管道长度花费。
思路：比较明显的最小生成树问题，相邻两点之间连一条边，边权为高度之差，求图的最小生成树即可。由于高度范围只有100，故可以直接类似hash表存了，无需排序。
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 | #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>#include <cmath>#include <algorithm>using namespace std;vector<pair<int, int> > C[101];int fa[1234567], a[1234567];int get_id(int x, int y, int n) { return x * n + y; }void add(int u, int v) { int dif = abs(a[u] - a[v]); C[dif].push_back(make_pair(u, v));}int getfa(int u) { return u == fa[u]? u : fa[u] = getfa(fa[u]); }int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int T; cin >> T; for (int cas = 1; cas <= T; cas ++) { int n, m; cin >> n >> m; for (int i = 0; i < 101; i ++) C[i].clear(); for (int i = 0; i < n * m; i ++) fa[i] = i; for (int i = 0; i < n; i ++) { for (int j = 0; j < m; j ++) { scanf("%d", a + get_id(i, j, m)); if (i) add(get_id(i, j, m), get_id(i - 1, j, m)); if (j) add(get_id(i, j, m), get_id(i, j - 1, m)); } } int cnt = 0, ans = 0; for (int i = 0; i < 101; i ++) { int sz = C[i].size(); for (int j = 0; j < sz; j ++) { int u = C[i][j].first, v = C[i][j].second; int fu = getfa(u), fv = getfa(v); if (fu != fv) { ans += i; cnt ++; fa[fu] = fv; if (cnt == n * m - 1) goto END; } } } END: printf("Case #%d:
", cas); cout << ans << endl; } return 0;} |