Some cables are already in the ground. Connect everything for the smallest extra cost.
What to build
Kruskal's algorithm, started from a network that is already partly built.
Requirements
- Existing cables cost nothing and are always kept.
- Add candidate cables, cheapest first, whenever one joins two groups that are not connected yet.
- Print the total extra cost, or -1 if the network cannot be connected.
Input
The first line has n, k and m. Each of the next k lines has an existing cable u v. Each of the next m lines has a candidate cable u v w.
Output
The smallest extra cost, or -1.
Constraints
1 ≤ n ≤ 100, 0 ≤ k ≤ 100, 0 ≤ m ≤ 500 and 1 ≤ w ≤ 1000.
Example
Input:
4 1 3
0 1
1 2 5
2 3 1
0 3 4
Output:
5
Why it works
Existing cables act like edges of weight 0, so Kruskal's greedy rule still applies. Once they are joined, each candidate is taken only if it connects two separate groups, and always the cheapest one that does.
Examples
4 1 3 0 1 1 2 5 2 3 1 0 3 4
5
3 0 1 0 1 3
-1
Hints
Hint 1
Join the existing cables in union-find first, at no cost.
Hint 2
Then run Kruskal's algorithm on the candidate cables, cheapest first.
Hint 3
At the end, check that there is only one group left.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
typedef struct {
int u, v, w;
} Edge;
int parent[100];
Edge edges[500];
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
int main(void) {
int n, k, m;
scanf("%d %d %d", &n, &k, &m);
for (int i = 0; i < n; i++) parent[i] = i;
int groups = n;
for (int i = 0; i < k; i++) {
int u, v;
scanf("%d %d", &u, &v);
int a = find(u), b = find(v);
if (a != b) {
parent[a] = b;
groups--;
}
}
for (int i = 0; i < m; i++) scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
for (int i = 1; i < m; i++) {
Edge e = edges[i];
int j = i - 1;
while (j >= 0 && edges[j].w > e.w) {
edges[j + 1] = edges[j];
j--;
}
edges[j + 1] = e;
}
int total = 0;
for (int i = 0; i < m; i++) {
int a = find(edges[i].u), b = find(edges[i].v);
if (a != b) {
parent[a] = b;
groups--;
total += edges[i].w;
}
}
printf("%d\n", groups == 1 ? total : -1);
return 0;
}