[hdu5253] 最小生成树，Kruskal

题意：有n*m个单位的农田，给定每个单位农田地势高低，现在需要灌溉所有农田，如果把水引入相邻的农田里需要的管道长度为两者的高度差。求最少的管道长度花费。

思路：比较明显的最小生成树问题，相邻两点之间连一条边，边权为高度之差，求图的最小生成树即可。由于高度范围只有100，故可以直接类似hash表存了，无需排序。

#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:\n", cas);

cout << ans << endl;

}

return 0;

}

巴特西

[hdu5253] 最小生成树，Kruskal

最新文章

热门文章