Here's my solution to Fenced In, Problem 3 from the USACO 2016 February Gold contest. My solution uses Kruskal's to calculate the cost of the MST formed by connecting the regions.
1// USACO 2016 February Gold Problem 3
2#include <iostream>
3#include <cstdio>
4#include <vector>
5#include <algorithm>
6using namespace std;
7void init(int n);
8bool unite(int a, int b);
9
10const int MAX_NM = 2000;
11struct Edge
12{
13 int from, to, weight;
14};
15
16int parent[(MAX_NM + 1) * (MAX_NM + 1)];
17int comp_size[(MAX_NM + 1) * (MAX_NM + 1)];
18int main()
19{
20 freopen("fencedin.in", "r", stdin);
21 freopen("fencedin.out", "w", stdout);
22 int a, b, n, m;
23 cin >> a >> b >> n >> m;
24 int vertical[MAX_NM], horizontal[MAX_NM];
25 for (int i = 0; i < n; i++)
26 {
27 scanf("%d", &vertical[i]);
28 }
29 sort(vertical, vertical + n);
30 for (int i = 0; i < m; i++)
31 {
32 scanf("%d", &horizontal[i]);
33 }
34 sort(horizontal, horizontal + m);
35 vector<Edge> edges;
36 edges.reserve(4 * n * m);
37 for (int x = 0; x <= n; x++)
38 {
39 for (int y = 0; y <= m; y++)
40 {
41 // edge with right
42 if (x + 1 <= n)
43 {
44 int bottom = (y - 1 >= 0 ? horizontal[y - 1] : 0);
45 int top = (y == m ? b : horizontal[y]);
46 edges.push_back({
47 (n + 1) * y + x,
48 (n + 1) * y + x + 1,
49 top - bottom
50 });
51 }
52 // edge with top
53 if (y + 1 <= m)
54 {
55 int left = (x - 1 >= 0 ? vertical[x - 1] : 0);
56 int right = (x == n ? a : vertical[x]);
57 edges.push_back({
58 (n + 1) * y + x,
59 (n + 1) * (y + 1) + x,
60 right - left
61 });
62 }
63 }
64 }
65 sort(edges.begin(), edges.end(), [](Edge a, Edge b){
66 return a.weight < b.weight;
67 });
68 init((n + 1) * (m + 1));
69 int num_regions = (n + 1) * (m + 1);
70 long long ans = 0;
71 for (Edge e : edges)
72 {
73 if (unite(e.from, e.to))
74 {
75 num_regions--;
76 ans += e.weight;
77 }
78 if (num_regions == 1)
79 {
80 printf("%lld\n", ans);
81 return 0;
82 }
83 }
84 return 0;
85}
86
87void init(int n)
88{
89 for (int i = 0; i < n; i++)
90 {
91 parent[i] = i;
92 comp_size[i] = 1;
93 }
94}
95
96int find(int a)
97{
98 if (a == parent[a])
99 {
100 return a;
101 }
102 return parent[a] = find(parent[a]);
103}
104
105bool unite(int a, int b)
106{
107 int roota = find(a), rootb = find(b);
108 if (roota == rootb)
109 {
110 return false;
111 }
112
113 if (comp_size[roota] > comp_size[rootb])
114 {
115 swap(roota, rootb);
116 }
117 comp_size[rootb] += comp_size[roota];
118 parent[roota] = rootb;
119 return true;
120}