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
66
67
68
69
70
71
72
73
74
75
76
77
78
|
// 1584. Min Cost to Connect All Points
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/*
* given a array 'points' representing integer coordinates of some points on a
* 2d-plane, where 'points[i] = [x[i], y[i]]'. the cost of connecting two points
* '[x[i], y[i]]' and '[x[j], y[j]]' is the manhattan distance between them:
* '|x[i], - x[j]| + |y[i] + y[j]|', where '|val|' denotes the absolute value of
* 'val'. return the minimum cost to make all points connected. all points are
* connected if there is exactly one simple path betwen any two points.
*/
int cmp(const void *p1, const void *p2) {
int *arr1 = *(int **)p1, *arr2 = *(int **)p2;
if (arr1[2] == arr2[2])
return arr1[0] - arr2[0];
return arr1[2] - arr2[2];
}
int UnionFind(int *UNION, int val) {
if (UNION[val] == val)
return val;
return UnionFind(UNION, UNION[val]);
}
bool UnionSet(int *UNION, int *Usize, int a, int b) {
int Find_a = UnionFind(UNION, a), Find_b = UnionFind(UNION, b);
if (Find_a == Find_b)
return false;
if (Usize[Find_a] > Usize[Find_b]) {
UNION[Find_b] = UNION[Find_a];
Usize[Find_a] += Usize[Find_b];
} else {
UNION[Find_a] = UNION[Find_b];
Usize[Find_b] += Usize[Find_a];
}
return true;
}
int minCostConnectPoints(int points[][2], int points_size,
int *points_col_size) {
int n = points_size, total_e = n * (n - 1) / 2, idx = 0;
int **table = malloc(total_e * sizeof(int *));
for (int i = 0; i < total_e; i++)
table[i] = malloc(3 * sizeof(int));
for (int i = 0; i < points_size; i++)
for (int j = i + 1; j < points_size; j++) {
table[idx][0] = i;
table[idx][1] = j;
table[idx][2] =
abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
idx++;
}
qsort(table, idx, sizeof(int *), cmp);
int *UNION = malloc(n * sizeof(int)), *Usize = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
UNION[i] = i;
Usize[i] = 1;
}
int ans = 0, edge = 0;
for (int i = 0; i < idx; i++)
if (UnionSet(UNION, Usize, table[i][0], table[i][1])) {
ans += table[i][2];
edge++;
if (edge == n - 1)
break;
}
return ans;
}
int main() {
int p1[5][2] = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}},
p2[3][2] = {{3, 12}, {-2, 5}, {-4, 1}};
printf("%d\n", minCostConnectPoints(p1, 5, NULL)); // expect: 20
printf("%d\n", minCostConnectPoints(p2, 3, NULL)); // expect: 18
}
|